.png&blockId=5f7573ad-6867-4d59-999e-722aced04aeb)
다이나믹 프로그래밍, 211113
문제
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
1.
X가 3으로 나누어 떨어지면, 3으로 나눈다.
2.
X가 2로 나누어 떨어지면, 2로 나눈다.
3.
1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.
입력
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
출력
첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.
예제 입력 1
2
Plain Text
복사
예제 출력 1
1
Plain Text
복사
예제 입력 2
10
Plain Text
복사
예제 출력 2
3
Plain Text
복사
힌트
10의 경우에 10 -> 9 -> 3 -> 1 로 3번 만에 만들 수 있다.
My solution
DP문제를 풀 때 점화식을 먼저 구해야 된다는 것을 위의 블로그를 보고 다시 기억했다. 그리고 top-down, bottom-up의 2개의 방식이 다 되는 것으로, 재귀만 가능한 게 아니라 반복문도 가능하다는 것도 알았다. DP문제를 풀어봤을 때 항상 DFS로 재귀적으로 접근했었는데 재귀로 풀어야 한다고 정하려면 반복문의 최대 횟수를 알고 그 값을 넘겨줄 수 있는 상황이 아니여야 한다.
여기서는 반복문(bottom-up)을 이용해서 문제를 풀었다. 왜냐하면 N이 주어지기 때문에 초기값 2개를 아는 상태에서 2~N까지 반복문을 돌리면 배열이 채워져서 원하는 값을 인덱스 N에 접근하면 바로 얻을 수 있기 때문이다.
0과 1은 1까지 변환할 필요가 없으니 횟수가 0이다.
2에 가능한 계산 방법은 -1 또는 /2 뿐이다. 비교를 해보자
•
2-1 = 1 이다. 결국 2가 1이 되는 횟수는 "1이 1이 되는 횟수" + 1 한 값과 똑같다.
•
2/2 = 1 이다. 결국 2가 1이 되는 횟수는 "1이 1이 되는 횟수" + 1 한 값과 똑같다.
•
2 /3 = 0 이다. 계산을 못한다. 위의 순서를 코드로 정리하면
•
d[2] = d[ 2- 1] + 1; // 먼저 하나의 값으로 기존의 0을 바꾸어주어야 한다.
•
if(2 % 2 == 0) d[2] = Math.min(d[ 2 / 2 ]+1, d[ 2 ]); // 만약 2로 나뉘어지면 그중 최솟값 선택
// 위에서 D배열에 현재 숫자의 횟수와 2로 나눴을때의 횟수를 비교해서 더 작은 값을 D배열에 넣는다.
3에 가능한 계산 방법은 -1 또는 /3 뿐이다. 비교를 해보자
•
3-1 = 2 이다. 결국 3이 1이 되는 횟수는 "2가 1이 되는 횟수" + 1 한 값과 똑같다.
•
3/3 = 1 이다. 결국 3이 1이 되는 횟수는 "1이 1이 되는 횟수" + 1 한 값과 똑같다.
•
3/2는 계산을 못한다. 위의 순서를 코드로 정리하면 위와 같은 순서대로 작은 문제의 정답을 기록해가면서 큰 문제를 푸는것이 다이나믹 프로그래밍 방법이다. 아래는 반복문으로 푼 방법이다.
•
d[3] = d[3-1]+1; // 먼저 하나의 값으로 기존의 0을 바꾸어주어야 한다.
•
if(3 % 3 == 0) d[3] = Math.min(d[3 / 3] +1 , d[3] );// 만약 3로 나뉘어지면 그중 최솟값 선택
// d[3/3] = d[1] = 0 +1 < d[3-1] = 2 => 1<2이므로 3으로 나누는 방법이 더 횟수가 작다.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int number = scan.nextInt();
int dp[] = new int[number+1];
dp[0] = 0;
dp[1] = 0;
// 초기 배열과 이미 알고 있는 2개의 값.
for(int i=2; i<=number; i++) {
dp[i] = dp[i-1] +1;
if(i%2 == 0)
dp[i] = Math.min(dp[i], dp[i/2]+1);
if(i%3==0)
dp[i] = Math.min(dp[i], dp[i/3]+1);
}
System.out.println(dp[number]);
}
}
Java
복사
반복문으로 구현해서 제출해본 다음 재귀를 이용해 Top-down 방식으로 구현해보려고 했다. 근데 런타임에러가 발생한다. 이건 최대 스택 사이즈를 벗어났을 가능성이 컸다.
function solution(i) {
const N = i.toString().trim() * 1;
// & : 반복문 - bottom-up
// const dp = Array(N + 1).fill(0);
// for (let i = 2; i <= N; i++) {
// dp[i] = dp[i - 1] + 1;
// if (i % 2 === 0) dp[i] = Math.min(dp[i], dp[i / 2] + 1);
// if (i % 3 === 0) dp[i] = Math.min(dp[i], dp[i / 3] + 1);
// }
//
let min = Number.MAX_SAFE_INTEGER; // 가지치기가 기존 min보다 커지면 더 진행하지 않게 함
function DFS(n, L) {
if (n === 1) {
min = Math.min(min, L);
return;
}
if (L >= min) return;
if (i % 2 === 0) DFS(Math.floor(n / 2), L + 1);
if (i % 3 === 0) DFS(Math.floor(n / 3), L + 1);
DFS(n - 1, L + 1);
}
DFS(N, 0);
// & : 반복문 - bottom-up
// console.log(dp);
// console.log(dp[N]);
// return dp[N].toString();
console.log(min);
return min.toString();
}
test('solution', () => {
expect(solution(`2`)).toStrictEqual('1');
expect(solution(`10`)).toStrictEqual('3');
});
JavaScript
복사
그래서 아예 다른 함수를 찾아다녔는데 위 재귀함수로는 풀리지않던 것이 더 깔끔한 다른 재귀 함수로 해보니 반례까지 통과가 되었다. 그리고 제출해서 정답으로 확인되었다.
function solution(i) {
const N = i.toString().trim()*1;
function solve(n) {
if (n === 0) return 0;
if (n === 1) return 0;
const quotient3 = Math.floor(n / 3);
const quotient2 = Math.floor(n / 2);
const mod3 = n % 3; // MODULO
const mod2 = n % 2;
return Math.min(solve(quotient3) + mod3 + 1, solve(quotient2) + mod2 + 1);
}
console.log(solve(N));
return solve(N).toString();
test('solution', () => {
// expect(solution(`2`)).toStrictEqual('1');
// expect(solution(`10`)).toStrictEqual('3');
expect(solution(`570`)).toStrictEqual('8');
expect(solution(`571`)).toStrictEqual('9');
expect(solution(`572`)).toStrictEqual('10');
expect(solution(`842`)).toStrictEqual('11');
});
JavaScript
복사
코드는 더 깔끔하지만 저런 공식을 도출하는 과정을 생각해내지 못했기 때문에 블로그를 읽어보면서 한번 정리해본다.
아 100%에서 틀리는 문제는 1을 입력으로 주었을 때 출력을 2로 주는 문제가 있었는데 이것은 input으로 들어온 숫자문자열을 숫자로 바꾸어주지 않아서 함수 내부에서 일치비교연산자를 사용했을 때 서로 타입이 다르기 때문에 다르다고 나오고 return 0이 되지 않았던 문제였다.
그래서 결과적으로 재귀가 가독성면에서도 조금 더 좋아보이긴 한다. 또한 재귀가 더 느린 실행속도를 가진 것으로 알고 있는데 이 경우에는 공식을 잘 만든 덕분에 더 빠른 성능을 보여준 것 같다.(188ms < 232ms)
재귀 호출이 중요한 이유는 크게 봐서 두 가지 인 것같다.
•
알고리즘 자체가 재귀적인 표현이 자연스러운 경우
•
변수 사용 을 줄일 수 있다.
탑-다운 관점으로 풀이
각 단계에서 2와 3으로 나눴을 때의 최솟값을 선택.
1을 빼는 것은 2와 3의 배수를 맞추기 위해서만 사용한다.
0과 1을 구하려고 할때는 그 값이 미리 정해져있는 0이 반환된다.
그 밖의 다른 N을 받게 되면 그 N을 분리하면서 들어가야한다.
일단은, 분리해서 들어가는데, 맨 아래에서 n이 0 또는 1이 되었을 때 return 0이 되면 mod3, mod2도 0또는 1이 들어오고 결과적으로 +1때문에 1과 2 중 최솟값을 가지고 거꾸로 올라온다.(원하는 값이 구해진다.) 그래서 위에 solve(3)을 보면 1 operation인 것이다.
이렇게 가져온 최솟값은 다른 편에서 만들어낸 최솟값과 또 비교를 한다.
여기서 중요한 부분은 아래의 부분이다.
const mod3 = n % 3; // MODULO
const mod2 = n % 2;
return Math.min(solve(quotient3) + mod3 + 1, solve(quotient2) + mod2 + 1);
JavaScript
복사
처음에 이해가 안갔었는데 저기 mod3이나 mod2를 더해주는 이유는 나머지로 남는 값은 2와 3으로 나눠지지 않는 것을 -1 연산을 통해서 맞춰주어서 -1연산의 횟수를 나타낸다. 그리고 해당 함수를 타고 들어가는 것 자체가 나누어서 몫을 전달해주는 연산이 있기 때문에 mod3 + 1이나 mod2 + 1로 되어있다.
solve(10)을 호출했을 때 solve(5) 쪽은 최솟값이 되지 않는 이유는
10 -> 5 → 4 → 2 → 1 이 되어 총 4번 연산을 하기 때문에 solve(3)의 3번 연산보다 더 많은 횟수의 연산이 필요하기 때문이다.
값을 누적시킬 때는 5에서 3과 2로 나누어보고 나누어 떨어지지 않지만 그 나머지를 연산횟수로서 더해주기 때문에 n이 0이 되거나 1이 되는 경우에 return 0;만 해주어도 -1 연산의 횟수는 자동으로 누적된다.
