🤍III [백준 1463/C++] 1로 만들기

BOJ 문제 보기

아직 열심히 배우는 단계입니다!🐣☘️
개선점 안내 혹은 잘못된 부분 지적, 질문 모두 환영합니다. 다양한 조언은 부족한 지식을 보완하는데 정말 큰 도움이 됩니다.🥰

---

1. 문제

다이나믹 프로그래밍의 기본이 되는 문제다. 바텀업 방식으로 해결할 수 있다.

---

2. 해결 과정

N=30일 때, /3, /2, -1을 이용해 1을 만드는 방법은 여러 가지가 있지만 연산을 최대한 적게 사용해야 한다.

두 경우를 비교해보자.

30을 어느 순서에 어떤 제수로 나누느냐에 따라 총 연산 횟수가 달라진다.

배열 d를 만들어 연산의 최소 횟수를 피제수마다 저장하고, 배열의 인덱스 i가 연산의 피제수라고 하자(d[(피제수)]). 위 예제로 하면 d[30]=4가 되겠다. d[0]과 d[1]은 연산 횟수가 없으므로 미리 0으로 지정해두고, 반복문을 활용해 2부터 N까지 연산한 모든 결과를 차례로 대입한다. N마다 나누는 수의 순서에 따라 연산 횟수가 다를 수 있어 모든 경우를 비교해 가장 작은 값을 구해야 한다.

우선 i에서 1을 뺀 경우를 가정하자. 1을 빼면 연산 횟수는 한 번 증가하므로 d[i-1]에 1을 더해준 값이 i의 연산 횟수가 된다(d[i]). algorithm 라이브러리를 활용해 i를 2로 나눈 값과 3으로 나눈 값 중 더 작은 수를 비교한다.

배열의 0번째 인덱스부터 i-1번째 인덱스까지 모두 값이 들어있으면 i를 연산한 값(i-1, i/2, i/3)에 대한 연산 횟수(d[i(연산)])를 바로 꺼낼 수 있다. 일일히 다음 연산 횟수를 계산하지 않고 한 번씩만 결과를 갱신하므로(DP 특징!) 총 수행 시간은 O(N)이 된다.

---

3. 코드

---

4. 생각 정리

다이나믹 프로그래밍 이론을 공부하기 전 세 수의 연산 결과를 예측해 경우의 수로 나누어 코드를 작성했다.

예를 들어 n이 2로 나누어 떨어지지만 4로 나누어 떨어지지 않으면서 (n-1)이 3으로 나누어 떨어지면 1을 먼저 빼고 다음 반복문에서 n%3==0 조건문에 걸리게 하기 같은 …ㅎㅎ 경우의 수가 너무 많아질 뿐더러 내가 세운 조건문이 모든 n에 대해 이득이라는 보장도 없다. 제시된 입력마다 케이스가 유동적으로 바뀌는 문제는 모든 경우를 전부 확인하는 방법을 사용하자. 앞으로 명확히 증명할 수 없는 가정으로는 알고리즘 세우기 말기! 더 고민해보면 확실한 답안이 나올 거다.

DP는 아직 실버 몇 문제만 풀어보았지만, 쉬운 문제는 규칙을 찾아 계산 결과를 차례대로 배열에 넣으면 얼추 풀리는 듯하다. 규칙 찾기가 감이 잘 안 온다. 문제를 많이 풀어보고 점화식 세우는 감을 잡아야 하겠다.

+)

반례를 찾으러 질문게시판을 돌아다니다가 규칙을 찾는 문제가 아니라, 최적의 방법을 프로그램에게 찾아내게 하는 문제입니다. n/3, n/2, n-1 중 최적인 것을 프로그램이 고르면 되는 문제입니다. 라는 답변을 봤다! DP 문제를 만나면 무작정 규칙과 경우의 수만 찾으려고 해 많이 헤맨 것 같다. 이번주에 DP 이론은 꼭 다잡아보자.🤓