백준 12852 c++ "1로 만들기 2" -PlusUltraCode-

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

 

[필자 사고]

그래프 탐색으로도 풀 수있지만 필자는 동적프로그래밍을 이용하여 풀었다.

이 문제를 풀면서 오랜만에 부모추적 알고리즘을 사용했다.

매번 최소화 되는 지점마다 이전 idx의 위치를 현재 idx에 기록을 하게 되면 

나중에 부모추적을 할 수 있게 된다.

 

또한 top-down 보단 bottom-up을 하는게 문제를 푸는게 훨씬 수월함을 느꼈다.

 

[코드 해설]

2. 유효한 숫자 검사 (isInside 함수)

isInside(num) 함수는 num 값이 N 이하인지 확인한다.

• num ≤ N 이면 true 반환
• 그렇지 않으면 false 반환

이 검사는 N을 초과하는 연산을 방지하는 역할을 한다.

---

3. 최소 연산 횟수 및 부모 노드 업데이트 (findMinCountAndParent 함수)

이 함수는 dp[nextNum] 값을 업데이트하는 역할을 한다.

1. nextNum이 N 이하인지 확인 (isInside(nextNum))
2. dp[nextNum] 값을 최소값으로 갱신
3. parent[nextNum] 값을 nowNum으로 저장하여 이동 경로를 추적

---

4. 경로 역추적 (findParentRoute 함수)

이 함수는 parent 배열을 사용하여 N → 1로 가는 경로를 역추적한다.

1. cout << nowIdx << " "로 현재 위치 출력
2. nowIdx == 1이면 종료
3. 부모 인덱스 parentIdx = parent[nowIdx]를 찾고 재귀 호출

---

5. 동적 프로그래밍을 이용한 최소 연산 횟수 계산 (Game_Start 함수)

1. N 값을 입력받는다.
2. dp 배열을 INT_MAX - 1로 초기화하여 최댓값을 설정한다.
3. dp[1] = 0으로 초기값 설정 (1에서 1까지 연산 횟수는 0)
4. parent 배열을 -1로 초기화하여 경로 추적 준비
5. 1 → N까지 숫자를 확인하면서 가능한 연산(×3, ×2, +1)을 수행
6. dp[N] 값이 갱신될 때 findParentRoute(N)을 호출하여 경로 출력

---

6. 결과 출력

1. dp[N] 값을 출력 → 최소 연산 횟수
2. findParentRoute(N) 호출 → 연산 경로 출력

---

7. 전체 코드 흐름 요약

1. N을 입력받는다.
2. dp와 parent 배열을 초기화한다.
3. DP를 이용하여 최소 연산 횟수를 계산
4. parent 배열을 활용하여 역추적(Backtracking) 을 수행
5. 결과를 출력한다.

[소스 코드]

#include <iostream>
#include <vector>
#include <cmath>
#include <climits>
using namespace std;

int N;
vector<int> dp;
vector<int> parent;

bool isInside(int num) {
	if (num <= N)return true;
	return false;
}

void findMinCountAndParent(int nextNum, int nowNum) {
	if (isInside(nextNum) == false)return;

	if (dp[nextNum] > dp[nowNum] + 1) {
		dp[nextNum] = dp[nowNum] + 1;
		parent[nextNum] = nowNum;
	}
}

void findParentRoute(int nowIdx) {
	cout << nowIdx << " ";
	if (nowIdx == 1)return;
	int parentIdx = parent[nowIdx];
	findParentRoute(parentIdx);
}

void Game_Start() {
	cin >> N;

	dp.resize(1000001,INT_MAX-1);
	dp[1] = 0;
	parent.resize(1000001, -1);
	for (int nowNumber = 1; nowNumber <= N; nowNumber++) {
		
		if (nowNumber == N) {
			cout << dp[N] << '\n';	
			findParentRoute(N);
		}

		int nextNumber1 = nowNumber * 3;
		int nextNumber2 = nowNumber * 2;
		int nextNumber3 = nowNumber + 1;
		
		findMinCountAndParent(nextNumber1, nowNumber);
		findMinCountAndParent(nextNumber2, nowNumber);
		findMinCountAndParent(nextNumber3, nowNumber);
	}
}

int main(void) {
	Game_Start();
}