3687 : 성냥개비 ( 백준 / java )

www.acmicpc.net/problem/3687

3687번: 성냥개비

 

 

 

*해결과정

 

 이 문제는 느낌상 dp였다. 하지만... dp는 항상 어렵다.. 특히 이 문제는 더욱 어려웠다. 규칙을 찾는 방식이 너무 독특했다. 먼저 dp에서 가장 핵심은 구해야 하는 것이 무엇이냐!?이다. 우리는 가장 작은 수와 큰 수를 구해야한다. 즉 dp에 저장되는 값들은 성냥을 이용한 갯수도 아니고 어떤 종류도 아니고 가장 작은 수, 큰 수가 저장되어야 하는 것이다. 따라서 2개의 dp배열을 만들어야 하며 100이 최대이므로 100개 전부 구해보도록 한다. 

 

 먼저 초기 조건을 구해야한다. 위의 그림은 1~9,0이 있는데 각각 몇 개의 성냥이 필요한지 계산한다. 초기 조건의 느낌이 난다.... 출력은 입력된 성냥의 갯수에 따라 작은 수, 큰 수를 구해야 하기 때문에 성냥갯수는 배열의 인덱스이다!

1	2	3	4	5	6	7	8	9	0
2	5	5	4	5	6	3	7	6	6

 

int[] minDp = new int[101];
int[] maxDp = new int[101];

 

일단 한번 무작정 최소값 , 최댓값을 구해본다.

갯수	8	9	10	11	12	13	14	15
최소	10	18	22	20	28	68	88	108
최대	1111	711	1111	71111	111111	711111	111111	7111111

 

그리고 문제에 주어진 0~9를 성냥의 갯수대로 dp를 초기화한다. dp의 시작은 초기 조건을 정해주는 것!!!!

0	1	2	3	4	5	6	7	8	9
0	0	1	7	4	2,3,5	0,6	8	-	-

 

 dp초기 조건이 대충 보이지 이제 이후의 규칙을 찾아보자. 이제 다시 위에 표와 합쳐서 보면....... 예를 들어 성냥 8개로 만드는 최소의 수 minDp[8] 값은 minDp[2] + minDp[6] 이다. (값을 더하는게 아니라 String으로 서로 값을 이어붙이는 것이다.)  즉 앞에 있는 dp값으로 최선의 답을 찾으면 된다!!

 

 성냥 10개로 만드는 최소의 수 minDp[10] 값은 minDp[5] + minDp[5] 이다. 이전의 dp값과 초기조건의 범위만큼 중에 적절하게 배열을 선택해서 최선의 선택을 해야한다. 이전의 dp값과! 초기조건에 대한 새로운 배열 add!를 활용해 dp값을 찾는다. (아래의 계단 오르기 문제와 비슷하다.)

 

escapefromcoding.tistory.com/146

2579번 : 계단 오르기 ( 백준 / java )

 

 이 문제는 직접 손으로 표를 만들면서 최소 숫자, 최대 숫자를 만들어보지 않았다면 규칙을 발견할 수 없었을 것이다.

 

*가장 작은 숫자

  가장 큰 어려움은 최솟값을 구할 때 초기 조건이 7까지 선정하는 것이 아니라 8까지 선정했다는 것이다. 그래야 답이 나온다. 바꿔 말하면,,, 7로 해서 답이 나오지 않는다면 적절하게 초기조건을 변경해봐야 한다는 것이다!!! 또한 overflow를 방지하기 위해서 초기 minDp의 값을 모두 max값으로 초기화 해준다. String[] add를 만들어 dp값과 적절하게 값을 확인하면서 최선의 dp를 찾으면 된다.

 

*가장 큰 숫자

최대값의 경우, 규칙이 더 간단하다.

홀 수 일 때 : 맨 앞은 7, 뒤에 나오는 숫자들은 1

짝수 일 때 : 모두 1

 

 

import java.util.*;
public class Main {

	static int N;
	static long[] minDp;
	static String[] maxDp;
	static int M;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		
		minDp = new long[101];
		maxDp = new String[101];
		
		Arrays.fill(minDp, Long.MAX_VALUE);
		minDp[2]=1;
		minDp[3]=7;
		minDp[4]=4;
		minDp[5]=2;
		minDp[6]=6;
		minDp[7]=8;
		minDp[8]=10;
		
		String[] add = {"1","7","4","2","0","8"};
		
		for(int i=9;i<=100;i++) {
			for(int j=2;j<=7;j++) {
				String line = minDp[i-j]+add[j-2];
				minDp[i] = Math.min(Long.parseLong(line), minDp[i]);
			}
		}
		
		String[] add2 = {"0","0","1","7","4","2","6","8"};
		maxDp[2] = "1";
		for(int i=3;i<=100;i++) {
			String line = "";
			if(i%2==0) { //짝수면
				for(int k=0;k<i/2;k++) {
					line += "1";
				}
			} else {
				int val = i/2-1;
				for(int k=0;k<val;k++) {
					line += "1";
				}
				line = add2[i-(val*2)] +""+line;
			}
			maxDp[i] = line;
		}
		
		for(int i=0;i<N;i++) {
			M = sc.nextInt();
			System.out.println(minDp[M]+" "+maxDp[M]);
		}
	}

	}

 

*dp 문제 해결순서 

1. 문제해결 요구에 따라서 dp배열에 담길 컨셉 정하기

2. 초기 조건 구하기

3. 이전의 dp값과 기존의 배열 값을 조합하여 계속 dp값을 구해나가기