[BOJ] 1463. 1로 만들기 (Java)

문제 링크 / level: Silver III

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

 

내가 생각한 풀이

어제부로 동적 계획법(DP)의 세계에 발을 들이게 되었다. 이론은 공부했는데, 실제 문제를 풀어봐야할 것 같아서 초고수 형님들의 추천 문제부터 풀어보았다. 그 첫 번째 문제가 바로 이것!

 

동적 계획법은 쉽게 말해서 큰 것을 잘게 쪼개서 풀긴 푸는데, 앞에서 구한 값을 이용해서 내가 최종적으로 원하는 값을 구해내는 기법이다. 대표적인 예제는 피보나치 수열이 있다. 지금까지 피보나치 수열을 구할 때는 재귀함수로만 풀 줄 알았지....인 줄 알았으나 알고보니 내가 사용했던 메모이제이션 기법이 곧 DP였다고 한다.😲💦

다만 내가 [2748.피보나치 수 2]에서 구현한 코드는 재귀를 사용한 하향식(top-down) 접근방법이었던 거고, 재귀 대신 반복문을 활용해 가장 작은 것부터 내가 원하는 값까지 점점 커지는 방향이라면 상향식(bottom-up) 방식이라고 한단다. 짝꿍 덕분에 이해가 쏙쏙 잘 됐다👩❤️

 

문제의 핵심 (출처: BOJ)

이 문제는 주어진 입력값 N을 3가지 연산을 통해 이러쿵 저러쿵해서 결론적으로는 1을 만드는 것이 목표다. 단, 이때 연산의 횟수가 최소가 되도록 해야하는 것이 핵심이며 그때의 연산횟수를 출력하는 것이 문제다.

 

점화식을 찾아보자~~!

띠용...............!😲

DP는 결국 문제에서 점화식을 이끌어내는 것이 핵심이다. 피보나치의 경우, 규칙이 뚜렷하고 우리가 익히 배워서 알고 있는 점화식이기 때문에 쉽게 구현해볼 수 있었지만.. 실전 문제를 풀어보려고 하니 점화식을 끌어내는 것부터 굉! 장! 히! 어려웠다.

이래서 알고리즘을 공부할 수록 수학 공부도 열심히 한다는건가보다.😞 (수학 잘하는 사람들은 멋있기도 하고, 알고리즘 할 때도 유익(?)할테니까 부럽다 부러워~)

 

혼자 끙끙대며 고민해봤지만 사실 피보나치 수열처럼 명확한 점화식이 보이질 않아서 도대체 어떻게 하라는거지? 싶은 생각만 들길래, 감을 잡기 위해 몇몇 초고수 형님들의 블로그를 참고해서 아이디어를 얻었다.

---

우선 점화식이니까 소위 말하는 base case를 생각해봐야 한다.

여기에서는 d[1] = 0 으로 설정해줄 수 있다. 왜냐? 1에서 1을 만드는데 필요한 연산은 0개이기 때문에. 이미 1이잖아!

 

그 다음부터가 문젠데, 가만 보면 1번 규칙: X가 3으로 나누어 떨어지면, 3으로 나눈다.는 왠지 3의 배수와 관련이 있어 보이고, 2번 규칙: X가 2로 나누어 떨어지면, 2로 나눈다.는 2의 배수와 관련이 깊어보인다^_^ 이를 활용해보도록 하자.

 

DP는 앞에서 연산한 결과들과 그 뒤에 연산할 것들을 최대한 잘 엮는(?) 것이 중요한 듯하다.

그래서 기본적으로는 d[1] = 0 라는 결과값을 토대로 d[2] = d[1] + 1 와 같이 표현해볼 수 있다. 3번 규칙에 의해 N=1일 때의 연산 횟수에서 1만 추가해주면 N=2일 때의 연산 횟수라고 볼 수 있는 것이다. 하지만 N=3일 때는 d[3] = d[2] + 1 와 같이 표현하면 최솟값이라는 조건을 만족하지 못한다. 왜냐? 1번 규칙에 의해 3/3 = 1 로 계산하면 1번만에 1로 만들 수 있기 때문이다. (위의 점화식을 활용하면 2라는 결과값이 나오는데 반해)

 

즉, 기본적으로 d[n] = d[n-1] + 1 라는 점화식을 통해 연산을 해주지만 N이 2의 배수이거나 3의 배수일 때는 각각  d[N/2] + 1 또는 d[N/3] + 1 와 같은 형태로 계산해준 뒤, 둘 중 최소인 값을 취하면 되겠다. 이제 슬슬 답에 거의 다다른 것 같다.🤗🎉

 

 

직접 해보니 내 코드에서는 N=30일때 문제가 생겼다.

※주의할 점: 나는 여기서 2의 배수와 3의 배수를 각각 if와 else if로 처리하는 만행(?)을 저질러 반례를 찾는데 애 좀 먹었다. if-else if가 아니라 각각 따로 if문을 걸어줘야하는데, 그 이유는 if-else if로 하면 2와 3의 공통 배수, 즉, 6의 배수의 최소 연산 수를 찾을때 문제가 생기기 때문이다. 직접 해보니 N=6, 12, 18, 24까지는 if-else if로 해도 차이가 없었는데, N=30에서 차이가 생겼다.

그리고 내가 참고했던 반례는 100000인데 결과값이 18이 나와야한다. (나는 19가 나왔었음)

 

// 핵심 코드
d[1] = 0;
for (int i = 2; i < N+1; i++) {
	d[i] = d[i-1]+1;
	if(i%2==0) {d[i] = Math.min(d[i], d[i/2]+1);}
	if(i%3==0) {d[i] = Math.min(d[i], d[i/3]+1);}
}

참고로 배열의 크기는 입력되는 값 N보다 하나 크게 해줬는데 그 이유는 인덱스와 실제 숫자 사이의 차이로 인한 혼선을 빚지 않기 위해서다. 즉, N=30일때 결과값이 궁금하다면 d[30]을 출력해주면 된다는 뜻이다.😎

 

그리고 성공!!

기분이가 너무 좋다~~~~!!!

조금씩 성장해나가는 이 느낌^_^ 삘쏘굿~~~~👍

 

다음문제는 처음부터 끝까지 온전히 다 내가 풀어봐야겠다. - 끝 -