[백준 3687번] 성냥개비

난이도: 골드 II

문제 링크: https://www.acmicpc.net/problem/3687

3687번: 성냥개비

 

제가 느끼기에 이 문제는 DP와 그리디를 이용하는 부분으로 나뉩니다.

그리디를 이용하는 부분은 최댓값을 구하는 부분으로, 상대적으로 더 쉽습니다.

성냥개비가 짝수개 있을 때는, 모두 1을 만들면 됩니다 (자릿수를 크게 함).

1을 만드는 데 성냥개비가 2개 소모되므로, 총 (성냥개비 개수 / 2)개의 1을 출력합니다.

성냥개비가 홀수개 있을 때는, 맨 앞자리에 7을 출력하고, 나머지 성냥개비로 1을 만들면 됩니다.

7을 만드는데 성냥개비가 3개 소모되고, 따라서 7 + (성냥개비 개수/2 - 1)개의 1을 출력합니다.

 

최솟값을 구하는 경우에는 DP를 사용해야 합니다.

성냥 n개를 이용하여 만들 수 있는 가장 작은 수를 몇 개 구해보면 다음과 같습니다.

match_min[] = {0, 0, 1, 7, 4, 2, 6, 8, 10}.

성냥의 개수	0	1	2	3	4	5	6	7	8
만드는 숫자	0	0	1	7	4	2	6	8	10

위의 표는 쉽게 계산할 수 있으므로, 이를 활용하여 DP 배열을 작성해 보겠습니다.

 

n = 9라면,

dp[9] = min(dp[9], dp[9-j]*10 + match_min[j])의 형태가 됩니다. 이 때 j는 [3, 8)이 되는데, 성냥은 최소 2개가 있어야 숫자를 만들 수 있고, 한 자리 숫자를 만드는 데는 최대 7개의 성냥이 소모되기 때문입니다.

 

이를 이용하여 아래와 같이 DP 배열을 작성하는 loop을 구성할 수 있습니다.

for (int i = 9; i <= 100; i++) {
	//성냥 2개를 빼서 1을 만들고, 남은 성냥으로 만들 수 있는 가장 큰 수가 10의 자리가 됨.
	dp[i] = dp[i-2]*10 + match_min[2];
    
    for (int j = 3; j < 8; j++) {
    	dp[i] = min(dp[i], dp[i-j]*10 + match_min[j];
    }
}

 

전체 코드는 아래와 같습니다.

 

 

성냥개비의 개수가 최대 100개이므로 위처럼 DP 테이블을 미리 작성한 후, 각 테스트 케이스에선 이미 기록된 값을 꺼내어 보기만 하면 됩니다.

 

채점 결과

 

점화식 떠올리기 어렵네요 ㅠㅠ