문제 https://www.acmicpc.net/problem/2885 2885번: 초콜릿 식사 학교 근처 편의점에 새 초콜릿이 들어왔다. 이 초콜릿은 막대 모양이고, 각 막대는 정사각형 N개로 이루어져 있다. 초콜릿의 크기(정사각형의 개수)는 항상 2의 제곱 형태이다. 즉, 1, 2, 4, 8, 16, ... www.acmicpc.net 풀이 초콜릿 나누기 문제 K 만큼의 초콜릿 조각을 만들려면 K 보다 큰 2^n의 크기의 초콜릿이여야 한다. 만약 나누어지면 정답을 출력한다. 그리디 문제는 쉽게 보여도 많이 어렵다. 제출 코드 # 2023/02/14 그리디 # https://www.acmicpc.net/problem/2885 K = int(input()) two = [] p = 1 # 초콜릿 크기는 K..
문제 https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 풀이 목적지까지 도달할 때 사용 하는 거울의 최소 값을 출력하는 문제 맨 처음 풀었을 땐 단순히 한쪽 방향으로 계속 진행시키고 만약 도달한 경우 정답을 출력하는 방법으로 문제를 해결했었다. 재채점 이후 시간초과가 발생했는데 그 이유는 중복방문 때문이었다. 따라서 해당 문제를 해결하기 위해 방문 기록을 들어온 방향에 따라 저장할 수 있도록 구현해서 문제를 해결했다. 제출 코드 1(시간..
문제 https://www.acmicpc.net/problem/27453 27453번: 귀엽기만 한 게 아닌 한별 양 첫 번째 줄에 마을의 세로 크기 $N$, 가로 크기 $M$, 한별이가 연속해서 막을 수 있는 불상사의 개수 $K$가 주어진다. ($2\leq N,M\leq 1\,000$, $0\leq K\leq 27$) 다음 $N$ 개의 줄에 걸쳐 마을의 상태가 주어진 www.acmicpc.net 풀이 지나온 3칸의 불상사 합과 이전에 들렀던 칸은 이동할 수 없다는 것을 생각해서 구현해야 하는 문제 갈 수 없는 곳의 조건 설정을 잘해야 한다. 내가 설정한 갈 수 있는 조건은 다음과 같다. 벽("X")이 아닌 경우 이전에 방문했던 곳(item)이 아닌 경우 방문하지 않았거나(-1) 해당 구역의 불상사가 다..
문제 https://www.acmicpc.net/problem/16637 16637번: 괄호 추가하기 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 www.acmicpc.net 풀이 괄호를 잘해서 가장 높은 값을 만드는 문제 짝수인 인덱스에는 숫자가 들어가고 홀수인 인덱스에는 연산 기호가 들어간다. 평범하게 계산한 경우와 괄호를 친 경우를 통해 결과를 찾아낸다. 위의 경우를 생각해 내기가 많이 까다로웠다. 제출 코드 # 2023/02/12 BruteForce # https://www.acmicpc.net/problem/16637 import sys ..
문제 https://www.acmicpc.net/problem/3184 3184번: 양 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다. www.acmicpc.net 풀이 늑대와 양의 수를 구하는 BFS문제 한 공간에 양이 더 많으면 늑대의 수는 0이 되고, 늑대가 더 많거나 같은 경우는 양들의 수는 0이 된다. 전 지역을 탐색할 때 벽이 아닌 경우, 해당 공간에서 움직일 수 있는 모든 구역을 조사한 뒤 양의 수와 늑대의 수를 비교해서 정답을 구한다. 제출 코드 # 2023/02/10 BFS # https://www.acmicpc.net/pr..
문제 https://www.acmicpc.net/problem/25916 25916번: 싫은데요 $6$번째 구멍부터 $8$번째 구멍까지 막으면 총 $9$의 부피를 소모하고, 최대값인 $9$를 출력한다 www.acmicpc.net 풀이 햄스터가 막을 수 있는 최대 크기를 출력하는 문제 두 포인터로 맨 처음부터 끝까지 탐색을 해본다. 부피가 부족하면 end + 1, 최대로 막을 수 있는 부피를 넘으면 start + 1을 하여 end가 N과 같아질 때까지 탐색한다. 제출 코드 # 2023/02/09 두 포인터 # https://www.acmicpc.net/problem/25916 import sys input = sys.stdin.readline # 두 포인터를 이용한다. def search(): res = ..
문제 https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 풀이 모든 경우를 탐색하는 bruteforce 문제 특정 높이에 따른 결과가 어떤지 비교하여 최소 시간과 그중 가장 높은 블록의 높이를 출력한다. 블록을 부술 때 인벤토리에 블록이 들어온다는 점을 잘 생각해야 한다. 제출 코드 # 2023/02/08 bruteforce # https://www.acmicpc.net/problem/18111 import sys input = sys.stdin..
문제 https://www.acmicpc.net/problem/1450 1450번: 냅색문제 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 109보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 주어진다. 무게도 109보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 meet in th middle 알고리즘과 이진 탐색을 이용하여 풀어야 하는 문제 처음에 배열을 두 개로 분리한 뒤 왼쪽의 부분 집합과 오른쪽의 부분 집합의 합을 이용해 정답을 구하는 문제이다. 배얼을 두개로 분리한 이유는 길이가 40인 배열의 완전 탐색은 2^40번을 탐색해야 한다. 그러나, 반반으로 나누면 2^20 * 2이므로 확실히 드는 시간이 줄어듦을 알 수 있다. 제출 코드 #..
