문제 www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 풀이 아래의 그림을 통해 점화식을 간단하게 표현할 수 있다. f(n)은 n만큼의 너비를 지니는 타일을 채우는 경우의 수이며 g(n)은 f(n)에서 1x1만큼의 타일을 빼고 채우는 경우의 수다. f(n)는 n이 홀수일 때 f(n) = 0이 되고, g(n)은 n이 짝수일 때 g(n) = 0이 된다. 이를 고려하여 base case를 처리한다. 코드 def solve(n): if n % 2 != 0: return 0 for i in range(2, n+1, 2): f[i] = f[i-2] + 2*g[i-1] for j i..
문제 www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 풀이 최단 거리와 관련된 그래프 탐색 문제는 너비 우선 탐색(BFS)를 통해 해결한다. 큐에 좌표(y,x)와 함께 이동횟수(cnt)를 함께 삽입하여 탐색시 1씩 증가하게 한다. 만약 이동하려는 칸의 좌표에 도달하면 이동횟수를 출력하고 탐색을 종료한다. 코드 import sys, collections dx = [-2, -2, -1, -1, 1, 1, 2, 2] dy = [1, -1, 2, -2, 2, -2, ..
문제 www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 k 0 1 2 3 4 5 6 7 8 9 10 coin 0 0 0 0 0 0 0 0 0 0 0 1 1 0+1=1 0+1=1 0+1=1 0+1=1 0+1=1 0+1=1 0+1=1 0+1=1 0+1=1 0+1=1 2 1 1 1+1=2 1+1=2 1+2=3 1+2=3 1+3=4 1+3=4 1+4=5 1+4=5 1+5 = 6 5 1 1 1 2 3 3+1=4 4+1=5 4+2=6 5+2=7 5+3=8 6+4=10..
문제 www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 풀이 쉬운 계단 수 문제와 아주 유사한 문제다. 하지만 수가 0으로 시작될 수 있다는 점에서 주의해야 한다. 맨 앞자리 수가 0이면 다음 숫자로 0~9까지 다 올 수 있으므로 dp[i][0] = dp[i-1][0] + dp[i-1][1] + ... + dp[i-1][8] + dp[i-1][9] 맨 앞자리 수가 1이면 다음 숫자로 1~9까지 올 수 있으므로 dp[i][1]..
문제 www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 풀이 문제가 약간 이상하다. 당연히 경우의 수를 구하는 것이기 때문에 중복을 제거해줘야 한다고 생각했는데 중복을 제거하면 틀리게 나온다. 조합을 사용하거나 재귀를 이용하여 풀 수 있다. 조합을 사용하는 방법이 더 직관적이지만, 재귀를 이용하는 방법이 메모리나 속도면에서 효율적이다. 리스트의 첫번째 인덱스에서 시작해서 해당 요소를 건너뛰고 다음 인덱스로 가거나 해당 요소를..
