문제https://www.acmicpc.net/problem/1463풀이n = int(input())memo = [0]*(n+1)for i in range(2,n+1): k=[memo[i-1]] if i%3==0: k.append(memo[i//3]) if i%2==0: k.append(memo[i//2]) memo[i] = min(k)+1print(memo[n]) 다이나믹 프로그래밍(DP) 문제이다.연산을 통해 n을 1로 만든다는 생각 보다는1부터 시작해서 n으로 만든다는 생각으로 풀이하였다. 어떤수 n을 만들기 위해 필요한 연산의 가짓 수는 총 3가지를 고려해야한다.1. n/3를 만드는데 필요한 연산 수 +1 (n이 3으로 나누어 떨어질 때)2. n/2를..

문제 https://www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 a = [int(input()) for i in range(int(input()))] target = max(a) save = [1] * (target + 1) save[1] = 1 save[2] = 2 save[3] = 4 for i in range(4,target+1): save[i] = (save[i-1] + save[i-2] + save[i-3])%1000000009 for i in a: print(save[i]%100000000..

문제 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 풀이 n = int(input()) memo = {} memo[1] = 1 memo[2] = 1 memo[3] = 1 memo[4] = 2 memo[5] = 2 def a(i): if i not in memo: memo[i] = a(i-1) + a(i-5) return memo[i] for i in range(n): print(a(int(input()))) 단순한 DP 문제이다. N이 1~5일때는..

문제 https://www.acmicpc.net/problem/11727 풀이 n = int(input()) dp = [-1]*(n+1) dp[0] = 1 dp[1] = 1 for i in range(2,n+1): dp[i] = 2 * dp[i-2] + dp[i-1] print(dp[n]%10007) 이 문제에서 2×N을 채우는 경우의 수는 세가지로 나뉜다. 1) 2×(N-2)를 채우고 = 모양을 더하는 경우 2) 2×(N-2)를 채우고 ㅁ 모양을 더하는 경우 3) 2×(N-1)을 채운 뒤 l 모양을 더하는 경우 즉, 2×N을 채우는 경우의 수는 2×(N-2)를 채우는 경우의 2배에 2×(N-1)을 더한 값이다. N=1일때 경우의 수는 1, N=2일때 경우의 수는 3이라는 것을 기본값으로 해서 동적계획법..

문제 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 풀이 n = int(input()) dp = [-1]*(n+1) dp[0] = 1 dp[1] = 1 for i in range(2,n+1): dp[i] = dp[i-2] + dp[i-1] print(dp[n]%10007) 이 문제의 정답 코드는 피보나치 수열을 구하는 방식과 동일하다. 그 이유를 살펴보자면 2×N을 채우는 경우의 수는 아래 두가지로 나뉜다. 1) 2×(N-2)를 채우고 = 모양을 더하는 경우 2)..