그릇 모으기 문제 n개의 그릇 더미가 있다 각 그릇 더미는 최대 h개의 그릇이 쌓여있고 항상 큰 그릇 위에 작은 그릇을 놓을 때 주어진 연산들을 사용하여 한 개의 그릇 더미로 만드는 최소 연산 횟수를 구하는 문제이다. 문제 풀이 문제를 좀 더 단순화하여 약한 조건으로 생각해보자.0번 그릇 더미를 새로 만들고 여기에 우리가 최후의 더미를 만든다는 조건과,모든 그릇의 크기는 각각 다르다는 조건을 추가해보면 우리는 주어진 접시들을 소팅한 후 가장 큰 접시부터 0번 그릇 더미위에 올리면 된다.따라서 현재 크기의 접시를 0번 그릇 더미 위에 올리는데 드는 연산 횟수는 다음과 같다.먼저 현재 크기의 접시를 해당 그릇 더미 맨 아래 (그보다 큰 접시는 이미 0번 그릇 더미로 옮겨 졌기 때문에) 에서 분리하기 위해서는..
A. Bear and Big Brother 문제 Limak 와 Bob의 몸무게가 주어진다. Limak는 매년 3배씩 커지고 Bob은 2배씩 커진다. Limak가 Bob보다 커지기 위해서는 최소 몇 년이 지나야 하는지 구하는 문제이다. 문제 풀이 단순하게 1년 씩 늘리면서 2와 3을 각각 곱하고, Limak가 커질 때 출력하면 된다. 소스 코드 B. Bear and Friendship Condition 문제 친구 관계가 그래프로 주어진다. 한 컴포넌트내의 모든 정점이 서로 연결되어 있는지(완전 그래프)인지 판별하는 문제이다. 문제 풀이 각 정점마다 연결된 간선이 해당 정점이 포함된 컴포넌트 크기 - 1 인지 확인한다. 소스 코드 C. Bear and Different Names 문제 N명의 군인이 있고, ..
운전 면허 시험 문제 (1,1)에서 (M,N)까지 이동하는데 남쪽과 동쪽으로만 이동할 수 있고 위 그림과 같이 이동하는데 길 상태에 따라 연료 g가 소모된다. 방향을 틀 때 1의 시간이 소모되고, 1개 변을 이동할 때 l 시간이 소모될 때 최대 가용 연료 G 이내로 들어올 수 있는 최소 시간을 구하는 문제이다. 문제 풀이 가장 쉽게 떠올릴 수 있는 풀이는 \(O(NMG)\) bfs 서칭 하는 방법이다. 물론 공간, 시간복잡도가 불가능한 풀이이고, 핵심적인 힌트는 이동하는데 걸리는 시간은 이동이 남쪽과 동쪽만 가능하므로 변의 개수는 의미가 없고 방향을 바꾼 횟수만 카운트해주면 된다는 점이다. 따라서 dp 테이블을 \(dp[x][y][k][dir]=(1,1)에서\: (x,y)좌표까지\: k번\: 방향을\: ..