코테/DP3 [java] 프로그래머스스쿨 연습문제 Lv.2 DP 문제 모음 2. 숫자 변환하기 코딩테스트 연습 - 숫자 변환하기 | 프로그래머스 스쿨 (programmers.co.kr) 풀이 1. 동적 계획법(Dynamic Programming) 아이디어를 활용한다. 2. 정수형 배열 dp를 크기 y+1로 선언한 후, 가능한 가장 큰 값(Integer.MAX_VALUE)으로 채운다. 3-1. 각 인덱스를 '만들 수 있는 값'으로 생각한다. 3-2. 각 인덱스 값을 만들기 위해 필요한 연산 횟수를 저장한다 3-3. 그러니까 """dp[ i ] 의 값은 곧 x가 i로 변환되기 위한 연산 횟수""" 인 것임 3-4. 이 과정은 memoization을 위한 것 4. 배열에 만들 수 있는 값을 인덱스로 삼아 최소 연산 횟수를 저장한다 4-1. for문으로 x부터 시작해 y까지 4-2. .. 2023. 4. 28. [C/C++] 백준 2775, Dynamic Programming 2775번: 부녀회장이 될테야 (acmicpc.net) 2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다 www.acmicpc.net #include #include #include using namespace std; int compute(int k, int n) { int B[2][15]; int tod = 0; //현재층 (i-1층) int tom = 1; //다음 층 (i층) for (int i = 0; i 2022. 12. 10. [C/C++] 백준 1463, Dynamic programming 1463번: 1로 만들기 (acmicpc.net) 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net * memoization이 아닌 recursive call을 사용하면 시간초과입니다. #include #include #include using namespace std; int min3(int a, int b, int c) { if (a < b && a < c) return a; else if (b < c) return b; else return c; } int make_one(int n) { vector arr(n + 1); int a = n; int b = n; int c = n; arr[1] = 0; for (int i.. 2022. 12. 10. 이전 1 다음
