22년 11월 1주차 회고록

public class 더하기123 { /* 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. */ //n이 11보다 작은 양수이기때문에 backtracking으로도 풀리지만, DP연습이기에 DP로 푼다. /* 1 = 1 2 = 1,1 || 2 3 = 1,1,1 || 1,2 || 2, 1 4 = 1,1,1,1 || 1,2,1 || 2,1,1 || 1,1,2 || 2,2 || 1,3 5 = 1,1,1,1,1 || 1,2,1,1 || 2,1,1,1 || 1,1,2,1 || 2,2,1 || 1,3,1 1,1,1,2 || 1,2,2 || 2,1,2 1,1,3 || 2,3 */ static int[] dp = new int[12]; public static int f(int n){ if(n == 1) return 1; if(n == 2) return 2; if(n == 3) return 4; // int result = dp[n]; // if(result != 0) return result; if(dp[n] != 0) return dp[n]; return dp[n] = f(n - 1) + f(n - 2) + f(n - 3); } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for (int i = 0; i < T; i++) { int N = sc.nextInt(); System.out.println(f(N)); } } }

import sys from itertools import product # 중복 순열 돌리기 # 10=3*3+1 -> 4 # 3^10 = 59049 -> 6만번 * 4 -> 24만번 -> 돌릴만함 # 메모리...? def how_many_case(x): case = 0 lower = (x-1) // 3 + 1 for i in range(lower, x+1): nums_list = product(range(1,4), repeat= i) for nums in nums_list: if sum(nums) == x: case += 1 return case testcase_num = int(input()) for i in range(testcase_num): testcase = int(sys.stdin.readline().replace("\n", "")) print(how_many_case(testcase))

DP를 사용하면서 점화식을 세우는 것이 어려웠습니다. 어떻게 한번 계산한 값을 저장 할지에 대한 방법을 생각하는것도 어려웠습니다.

점화식을 활용한 케이스 간의 관계를 파악하는 것이 어려웠습니다. 그래서 그냥 itertools를 이용해서 경우의 수를 다 구했는데, 이 케이스에서만 유용한 것 같아 점화식과 재귀함수를 이용한 풀이를 연습해야할 것 같습니다.

어떤 문제를 만났을때 DP를 사용해야 하는지 감을 잡은거 같습니다. 답이 작은 문제로 나누어지고 그 답이 최종 답과 연결되어있다면 DP를 생각해 보아야겠다고 느꼈습니다.

코딩 테스트에서 제시한 조건들을 잘 보는 것이 중요하다는 것을 깨달았습니다 제한 조건이 작은 경우는 그냥 반복문 돌려서 케이스를 다 구해도 된다는 것을 느꼈습니다. :)