문제 www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 풀이 일반적인 그래프 탐색 문제와 달리 z축까지 고려해야 하는 문제였다.최소 일수, 즉 최단 거리를 구해야 하기 때문에 BFS를 이용해야 한다. 모든 익은 토마토의 좌표를 큐에 담아주는 것이 중요하다. 어느 지점에서 탐색을 시작하는지 여부에 따라 최단 거리가 상이하게 구해지기 때문이다. 코드 import sys, collections def bfs(): result = 0 q = c..
문제 www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 풀이 처음엔 단순한 그래프 문제로 생각했는데, 잘 풀리지 않았다. 곰곰히 생각해보니 이전에 프로그래머스에서 풀었던 등굣길 문제와 유사했다. 좌표 (0, 0)부터 (n-1, n-1)까지 순회하며 현재 좌표(x, y)에서 오른쪽과 아래쪽으로 갈 수 있는지 검사하고, 만약 갈 수 있다면 dp[nx][ny]에 dp[x][y]를 더해준다. 이때 dp[y][x] == 0이면 건너뛰는 방식으로 최적화를 해줄..
문제 www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 풀이 유사한 문제들은 많이 풀어보았다. 1, 2, 3을 만들 수 있는 경우의 수를 dp테이블에 베이스로 저장해둔다. 점화식은 다음과 같다. dp[n] = dp[n-1] + dp[n-2] + dp[n-3] (3
문제 www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 풀이 이전에 풀었던 오르막 수 문제의 쉬운 버전 문제다. dp[n][0] = 0으로 끝나는 n자리 이친수의 개수 dp[n][1] = 1로 끝나는 n자리 이친수의 개수 문제에 주어진 조건을 살펴보자. 이친수는 0으로 시작하지 않는다. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. 1번 조건에 의해 dp[1][0] = 0, dp[1][1] = 1이 성립..
문제 www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 풀이 가장 큰 증가 부분 수열 문제의 응용 문제다. 이중 for문을 두 번 구성하여 dp[n][0]엔 왼쪽부터 증가하는 가장 긴 부분 수열의 길이를 기록하고, dp[n][1]엔 오른쪽부터 증가하는 가장 긴 부분 수열의 기록을 기록한다. 중복으로 겹쳐지는 부분이 있기 때문에 해를 구할 땐 1을 빼줘야 한다. 코드 import sys n = int(sys.stdin.readline().strip()) a = [int(x) for..
