[백준] S3 1463 1로 만들기 (java)

www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

풀이

 

1) path[N+1] 배열을 생성한다. 배열의 값은 1에서 해당 number에 도달하기위해 필요한 연산의 최소 횟수이다.

2) path 배열의 값을 1000000으로 초기화 시켜준다. (문제에서 10^6 까지라고 했으므로)

3) path[1] = 0 으로 초기화 한다. (1에서 1로 가는 연산의 횟수는 0이므로)

4) n = 2부터 N까지 for문을 돌면서 3가지 경우를 따진다

 

1. n % 3 = 0 인 경우 : path[n] = Math.min(path[n/3] + 1, path[n])
2. n % 2 = 0 인 경우 : path[n] = Math.min(path[n/2] + 1, path[n] )
3. 1을 빼는 경우 : path[n] = Math.min(path[n-1] + 1, path[n])

5) path[N] 을 출력한다.

 

 

 

주의사항

 

1) 경험을 쌓자

 

package com.baekJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BJ_S3_1463_1로만들기 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	static int N, path[];
	public static void main(String[] args) throws NumberFormatException, IOException {
		input = new BufferedReader(new StringReader(src));
		N = Integer.parseInt(input.readLine());
		path = new int[N+1];
		Arrays.fill(path, 1000000);
		path[1] = 0;
		for(int n=2; n<=N; n++) {
			path[n] = Math.min(path[n-1] + 1, path[n]);
			if(n%2==0) {
				path[n] = Math.min(path[n/2]+1, path[n]);
			}
			if(n%3==0) {
				path[n] = Math.min(path[n/3]+ 1, path[n]);
			}
		}
		System.out.println(path[N]);
	}
	static String src =
			"100000";
}

 

 

후기

 

 DP 문제가 약해서 쉬운 DP문제 없나 하고 찾아 풀어봤다.

처음엔 N 부터 1씩 감소하는 방식으로 코드를 작성하였는데 하면서도 뭔가 꼬이는 느낌이 들었고 역시나 제출해봤지만 틀렸습니다가 나왔다. 

결국 솔루션을 봐버렸다.

탐색은 실버따위 코파면서 한손으로 풀 수있었는데 DP는 실버 3따위가 겁나 어려웠다. 

솔루션을 보니까 맙소사.. 겁나게 간단한 코드를 보게되었고 사태의 심각성을 깨달았다.

아.. 나는 탐색밖에 못하는 바보 머저리였어..

오늘부터 탐색의 비중을 낮추고 그리디, DP문제들을 많이 풀어야 겠다고 생각하게되었다.