[백준_3687번] 성냥개비

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

3687번: 성냥개비

[문제]

성냥개비는 숫자를 나타내기에 아주 이상적인 도구이다. 보통 십진수를 성냥개비로 표현하는 방법은 다음과 같다.

 

성냥개비의 개수가 주어졌을 때, 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 큰 수를 찾는 프로그램을 작성하시오.

 

[입력 조건]

 첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개 이다. 각 테스트 케이스는 한 줄로 이루어져 있고, 성냥개비의 개수 n이 주어진다. (2 ≤ n ≤ 100)

 

[코드]

import java.util.*;

public class BaekJoon_3687 {
	static long[] mindp;
	static String[] maxdp;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int testcase=sc.nextInt();
		
		while(testcase-->0) {
			int n=sc.nextInt();
			
			mindp=new long[101];
			maxdp=new String[101];
			
			///////////////////작은 숫자 구하기///////////////////
			Arrays.fill(mindp,Long.MAX_VALUE);
			/*
			 * mindp[i]는 i개의 성냥개비를 사용하여 만들 수 있는
			 * 가장 작은 수를 저장하는 배열, 인덱스 2~8까지는 초기화 필요!
			 * 
			 * 이때 mindp[6]으로 만들 수 있는 숫자는 0,6 두 가지가 있지만 
			 * 0은 첫번째 자리에 올 수 없으므로 mindp[6]은 6으로 초기화 한다.
			 * 다른 숫자 뒤에 올 때는 6보다 작은 0을 사용한다.
			 */
			mindp[2]=1;
			mindp[3]=7;
			mindp[4]=4;
			mindp[5]=2;
			mindp[6]=6;
			mindp[7]=8;
			mindp[8]=10;
			String[] addmin= {"1","7","4","2","0","8"};
			
			// mindp의 값을 주어진 범위만큼 모두 구한다.
			for(int i=9;i<=100;i++) {
				/*
				 * 성냥개비 9개로 만들 수 있는 가장 작은수를 구하기 위한 경우의 수에는
				 * 2+7, 3+6, 4+5, 5+4, 6+3, 7+2가 있다. 
				 * 이때 1+8을 고려하지 않는 이유는 성냥개비 1개로 만들 수 있는 수는 없기 때문이다.
				 * 이처럼 만들 수 없는 수인 1,0은 고려하지 않아야 한다.
				 * 따라서 위에 적은 경우의 수를 모두 비교하여 가장 작은 수를 찾으면 된다. 
				 * 이때 주의해야할 점은 비교대상은 성냥개비로 만들어진 숫자이다. 
				 * 
				 * 점화식은 mindp[n]=(mindp[n-2]+addmin[2], mindp[n-3]+addmin[3], ..., mindp[n-7]+addmin[7])
				 */
				for(int j=2;j<=7;j++) {
					String str=mindp[i-j]+addmin[j-2];
					mindp[i]=Math.min(mindp[i],Long.parseLong(str));
				}
			}
			
			///////////////////큰 숫자 구하기///////////////////
			/*
			 * 큰 수는 1과 7만을 사용해서 만들 수 있다. 
			 * 성냥개비 8개를 사용해서 만들 수 있는 가장 큰 수는 1111
			 * 성냥개비 9개를 사용해서 만들 수 있는 가장 큰 수는 711
			 * 성냥개비 10개를 사용해서 만들 수 있는 가장 큰 수는 1111
			 * 성냥개비 11개를 사용해서 만들 수 있는 가장 큰 수는 71111
			 * 
			 * 즉, 큰 숫자를 만든다고 큰 수가 되는 것이 아닌 만드는데 성냥개비가 가장 적게드는 1을 사용하여
			 * 가장 긴 자릿수를 만드는 것이 큰 수를 만드는 방법이다. 
			 * 이때 성냥개비의 갯수가 짝수일 경우는 만들어지는 1의 개수가 딱 떨어지지만 
			 * 홀수인 경우에는 성냥개비 1개로 만들 수 있는 수가 없기 때문에 3개로 만들 수 있는 7을 사용해야 한다. 
			 * 
			 * 따라서 큰 수는 1과 7만을 사용해서 만들 수 있다. 
			 */
			StringBuilder max=new StringBuilder();
			int length=n/2; 
			if(n%2==1) // 홀수 인 경우 맨 앞 자리는 7
				max.append("7");
			else // 짝수인 경우에는 1
				max.append("1");
			// 위 과정에서 앞 자리는 채웠기때문에 -1한 값까지 1 채우기
			for(int i=0;i<length-1;i++)
				max.append("1");
			
			System.out.println(mindp[n]+" "+max);
		}
	}
}

 

[고찰]

 처음 이 문제를 접근한 방법은 백트래킹으로 가능한 모든 경우의 수를 탐색하는 것이었다. 하지만 오버플로우가 발생하면서 만들어질 수 있는 경우의 수가 너무 많다는 것을 알았다. 고민을 더 해봤지만 해결방법이 떠오르지 않아 다른 사람의 코드를 봤더니 DP 문제였다. 또한 포스팅을 봐도 이해가 잘 가지 않아 규칙을 이해하고, 푸는데만 이틀이 걸린 문제이다. 

 

http://blog.devjoshua.me/2019/11/30/boj-3687/

[BOJ] 3687 - 성냥개비

 위 블로그를 참고해서 풀었다. 너무 잘 정리해 놓으셨지만 스스로 한번 더 정리해보면서 이해를 도왔다.

 

*** 0) 규칙 찾기

dp문제라는 것을 알고난 후에는 dp 배열을 만들고, 초기화를 해야한다. 우선 0~9까지의 숫자를 만드는데 사용되는 성냥개비의 숫자부터 파악했다. 

 

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

 

사용갯수의 중복도 있기 때문에 성냥개비 사용 갯수를 중심으로 만들수 있는 수를 다시 정리해보자면 아래와 같다.

 

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

 

 여기서 찾아야 하는 것은 최소 숫자이기 때문에 중복된 개수의 성냥깨비를 사용하는 경우는 그 중 가장 작은 값을 선택하면 된다. 이때 주의해야할 점은 6개의 성냥개비를 사용하는 경우이다. 0은 맨 앞자리에 올 수 없지만 2자리 이상 만들어질 때는 0이 오는 것이 최솟값을 만들 수 있는경우이다. 따라서 dp[6]은 0으로 초기화 하지만 이후에 사용해야 하는 수는 0임을 명심해야 한다. 

 

이후 규칙을 찾기 위해 8부터 만들 수 있는 최솟값과 최댓값을 구해봐야 한다. 

 

성냥개비 갯수	2개	3개	4개	5개	6개	7개
최솟값	1	7	4	2	6	8
최댓값	1	7	4	2	6	8

                                 

성냥개비 갯수	8개	9개	10개	11개	12개	13개
최솟값	10	18	22	20	28	68
최댓값	1111	711	11111	71111	111111	711111

 

이 표를 활용하여 최솟값, 최댓값을 찾는 규칙을 발견할 수 있다. 

 

*** 1) 작은 수 찾는 법

성냥개비 9개로 만들 수 있는 가장 작은수를 구하기 위한 경우의 수에는 2+7, 3+6, 4+5, 5+4, 6+3, 7+2가 있다. 이때 1+8을 고려하지 않는 이유는 성냥개비 1개로 만들 수 있는 수는 없기 때문이다. 이처럼 만들 수 없는 수인 1,0은 고려하지 않아야 한다. 따라서 위에 적은 경우의 수를 모두 비교하여 가장 작은 수를 찾으면 된다. 이때 주의해야할 점은 비교대상은 성냥개비로 만들어진 숫자라는 것이다. 

 

3자리 숫자가 만들어질 때도 생각해봐야 한다. 15개의 성냥개비를 사용하여 최솟값을 만들 경우 나올수 있는 경우의 수는 1+14, 2+13,..., 13+2, 14+1로 15가 된다. 여기서 최솟값은 108이다. 이 값은 "2개로 만들 수 있는 최소숫자+6개로 만들 수 있는 최소숫자+7개로 만들 수 있는 최소숫자"이다. 달리 말하면 "8개로 만들 수 있는 최소숫자+7개로 만들 수 있는 최소숫자"가 된다. 즉 dp에 저장된 값을 활용하면 더 효율적으로 최솟값을 찾을 수 있다는 의미이다.

최종적으로 만들어지는 점화식은 mindp[n]=(mindp[n-2]+addmin[2], mindp[n-3]+addmin[3], ..., mindp[n-7]+addmin[7])이 된다. 

 

*** 2) 큰 수 찾는 법 

큰 수를 찾는 방법은 작은 수를 찾는 방법보다 훨씬 간단하다. 큰 수는 1과 7만을 사용해서 만들 수 있다.

 
-> 성냥개비 8개를 사용해서 만들 수 있는 가장 큰 수는 1111
-> 성냥개비 9개를 사용해서 만들 수 있는 가장 큰 수는 711
-> 성냥개비 10개를 사용해서 만들 수 있는 가장 큰 수는 1111
-> 성냥개비 11개를 사용해서 만들 수 있는 가장 큰 수는 71111

 

 즉, 큰 숫자를 만든다고 큰 수가 되는 것이 아닌 만드는데 성냥개비가 가장 적게드는 1을 사용하여 가장 긴 자릿수를 만드는 것이 큰 수를 만드는 방법이다.  이때 성냥개비의 갯수가 짝수일 경우는 만들어지는 1의 개수가 딱 떨어지지만  홀수인 경우에는 성냥개비 1개로 만들 수 있는 수가 없기 때문에 3개로 만들 수 있는 7을 사용해야 한다. 

 

 성냥개비의 개수가 짝수인지 홀수인지를 파악하여 맨 앞 자리 수를 7과 1 중에 선택하고, 1을 만들때 사용되는 성냥개비의 개수가 2개이기 때문에 성냥개비의 개수를 반 나눈 값-1 만큼 1을 붙여주면 된다. 이때 맨 앞자리수는 이미 정했기 때문에 -1을 해주어야 한다.