문제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/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 n = int(input()) numbers = list(map(int,input().split())) memo = [0]*n for i in range(n): target = [0] for j in range(i): if numbers[j] < numbers[i]: target.append(memo[j]) ..

문제 https://www.acmicpc.net/problem/12101 12101번: 1, 2, 3 더하기 2 n을 1, 2, 3의 합으로 나타내는 방법 중에서 사전 순으로 k번째에 오는 것을 출력한다. k번째 오는 식이 없는 경우에는 -1을 출력한다. www.acmicpc.net 풀이 n,k = map(int,input().split()) save = {} save[1] = ["1"] save[2] = ["1+1","2"] save[3] = ["1+2","1+1+1","2+1","3"] for i in range(4,12): save[i] = [] for j in save[i-1]: save[i].append(j+"+1") for j in save[i-2]: save[i].append(j+"+2") ..

문제 https://www.acmicpc.net/problem/1351 1351번: 무한 수열 첫째 줄에 3개의 정수 N, P, Q가 주어진다. www.acmicpc.net 풀이 n, p, q = map(int,input().split()) memo = {} memo[0] = 1 def a(i): if i not in memo: memo[i] = a(i//p) + a(i//q) return memo[i] print(a(n)) n의 크기가 0 ≤ N ≤ 10^12 로 매우 크므로 DP 중 tabulation 방식으로는 풀수가 없었다. 크기가 10^12인 배열을 생성하니 그냥 오류를 뱉어 버리더라... 그래서 딕셔너리와 재귀함수를 이용하여 memoization 방식으로 구현해주었다. 재귀함수를 통해 a(i)..

문제 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. 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] for i in a: print(save[i]) 테스트케이스 만큼 입력을 받고 가장 큰 수만큼 배열을 생성하여 그 이하 숫자에 대해서 ..