[BOJ - JAVA] 12852 - 1로 만들기 2 (DP, 그래프)

# 주소

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

12852번: 1로 만들기 2

# 문제

# 문제 해설 및 코드 리뷰

import java.util.*;
class Main{
	static int[] dp;
	static int n;
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();
		dp = new int[n + 1];
		Arrays.fill(dp, 1000000);
		dp[n] = 0;
		for(int i = n; i >= 1; i--) {
			int x = dp[i] + 1;
			if(i % 3 == 0)
				dp[i / 3] = Math.min(dp[i / 3], x);
			if(i % 2 == 0)
				dp[i / 2] = Math.min(dp[i / 2], x);
			dp[i - 1] = Math.min(dp[i - 1], x);
		}
		StringBuilder sb = new StringBuilder();
		sb.append(dp[1] + "\n");
		Stack<Integer> stack = new Stack<Integer>();
		int x = dp[1];
		for(int i = 1; i <= n; i++) {
			if(x == dp[i]) {
				stack.push(i);
				if(i * 3 <= n && dp[i * 3] == x - 1)
					i = i * 3 - 1;
				else if(i * 2 <= n && dp[i * 2] == x - 1)
					i = i * 2 - 1;
			}
			x--;
		}
		while(!stack.isEmpty()) {
			sb.append(stack.pop() + " ");
		}
		System.out.print(sb);
	}
}

 

요즘 프로젝트 개발 때문에 정신없는 하루를 보내고 있습니다.

개발 관련 포스팅도 쭉 이어나가야 하는데 에러 해결하는 과정들이 구글링을 하고 고쳐지면 "오 되네" 하고 다음 기능을 구현하기 일쑤라 따로 정리할 시간도 없이 개발하는 것 같아요 ㅠㅠ

그에 비해 알고리즘 문제들은 개별로 관리가 가능하다는 점에서 포스팅하기 용이한 것 같습니다.

CS는 지금 하는 프로젝트가 끝나면 본격적으로 시작해보려합니다.

이번 시간엔 이 블로그에는 생소할 수 있는 DP문제를 포스팅해보려 합니다.

DP는 제가 유달리 많이 약한 분야중 하나인데요..

코딩테스트를 한창 치고 있을 때 느낀게 DP가 나와도 너무 많이 나와서 공부 필요성을 느껴 풀게 되었습니다.

정작 BFS 보단 구현, DP, 문자열 등의 문제들이 요즈음 주를 이루는 것 같으니 경향 분석 잘 하셔서 대비하시길 바랍니다.

이번 문제는 먼저 문제를 분석한 뒤 코드를 살펴봅시다.

문제의 정답 조건은 "주어진 n값으로 1을 만드는 최소 경우의 수를 구하자"가 목표입니다.

저는 dp배열을 만들었으나 2차원 배열로 생성하여 구하고자 하였지만 예제는 다 맞아도 1%에서 자꾸 틀려, 게시판 반례들을 돌려봐도 해결해주진 못하였습니다. 이에, 다른 풀이를 찾아보았는데요.

제가 원래 짰던 코드는

import java.util.*;
class Main{
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int[][] dp = new int[n + 1][3];
		dp[0][0] = n;
		dp[0][1] = n;
		dp[0][2] = n;
		int nx = 0;
		int ny = 0;
		int count = 0;
		if(n == 1) {
			System.out.println(0);
			System.out.println(1);
			System.exit(0);
		}
		for(int i = 1; i <= n; i++) {
			boolean isEnd = false;
			count++;
			if(dp[i - 1][0] % 3 == 0)
				dp[i][0] = dp[i - 1][0] / 3;
			else dp[i][0] = dp[i - 1][0] - 1;
			if(dp[i - 1][1] % 2 == 0) 
				dp[i][1] = dp[i - 1][1] / 2;
			else dp[i][1] = dp[i - 1][1] - 1;
			if(dp[i][0] == 1) {
				nx = i;
				ny = 0;
				break;
			}else if(dp[i][1] == 1) {
				nx = i;
				ny = 1;
				break;
			}
		}
		StringBuilder sb = new StringBuilder();
		for(int i = 0; i <= nx; i++)
			sb.append(dp[i][ny] + " ");
		System.out.println(count);
		System.out.println(sb);
	}
}

다음과 같았습니다.

제가 짠 코드의 문제점은 "3으로 나눌 수 있지만 2로 나눌 수 있으면 그럼 무엇을 최솟값으로 가질지 알 수가 있는가?"에 대한 초점이라 생각합니다

따라서 이러한 방식은 잘못되었다고 생각하였고 이를 해결하기 위해 n에서부터 역추적하여 1까지 도달하는 시간복잡도 O(N)의 풀이를 진행하여야만 했습니다.

1부터 N까지 도달하는 방식은 반례가 많기 때문입니다.

따라서

for(int i = n; i >= 1; i--) {
			int x = dp[i] + 1;
			if(i % 3 == 0)
				dp[i / 3] = Math.min(dp[i / 3], x);
			if(i % 2 == 0)
				dp[i / 2] = Math.min(dp[i / 2], x);
			dp[i - 1] = Math.min(dp[i - 1], x);
		}

N에서부터 1까지 역추적 하기 위해 3으로 나누어 떨어지면 현재의 dp[i] + 1, dp[i/2]중 최솟값을 dp[i/3]에 담고 2로 나누어 떨어지면 dp[i] + 1, dp[i/2]중 최솟값을 담았습니다.

이로 인해 재방문한다 하더라도 최솟값이 갱신되기 때문에 문제될 부분이 전혀 없습니다.

또한 3으로 나누어지면서 2로 나누어진다 한들 우리는 개별로 관리하기 때문에 최솟값을 구할 수 있게됩니다.

다음 코드는 다음과 같습니다.

StringBuilder sb = new StringBuilder();
		sb.append(dp[1] + "\n");
		Stack<Integer> stack = new Stack<Integer>();
		int x = dp[1];
		for(int i = 1; i <= n; i++) {
			if(x == dp[i]) {
				stack.push(i);
				if(i * 3 <= n && dp[i * 3] == x - 1)
					i = i * 3 - 1;
				else if(i * 2 <= n && dp[i * 2] == x - 1)
					i = i * 2 - 1;
			}
			x--;
		}

출력값이 많아질 것을 대비해 StringBuilder를 사용했습니다.

근데 막상 최댓값을 넣어도 19인가 20밖에 안나와서 이거 안써도 정답에는 무리 없다 생각은 듭니다 ㅎ.

dp[1]을 x라고 선언합니다. 이 x를 이용하여 정답 경로를 담을 것입니다.

for문에서 x와 dp가 같다면 i를 stack에 담는데요. 

이 때 최소가 되는 경로는 오직 한 가지만 존재하기 때문에, i * 3이 되든, i * 2가 되든 i값을 계속해서 증가시켜주면서 최소 경로를 이번엔 정방향으로 찾아야 합니다.

while을 이용해서도 풀 수 있습니다.

최소가 되는 x를 찾아낼 때마다 x를 감소시주어야 하며 최종적으로 스택에는 최소경로를 담게 됩니다.

이를 sb에 다시 역으로 pop하여 저장하고 정답으로 출력하시면 정답이 될 수 있답니다.

감사합니다.

 

ps. DP는 너무너무너무 어렵습니다.