성냥 개비
Last updated
Last updated
성냥개비 n개로 만들 수 있는 최솟값과 최댓값을 구하라.
먼저, 문제에서 제시한 성냥개비로 만든 10진수는 전체 해를 구하는 데에 필요한 최소한의 부분해("최초 조건")가 된다. 최솟값 : minDP, 최댓값 : maxDP 총 2개의 DP 배열이 필요하다. n은 2이상 100이하라고 했기 때문에 성냥개비 100개로 만들 수 있는 최솟값과 최댓값 다 구해보면 된다.
최솟값 구하기 : 최솟값은 자릿수 갯수가 작아야한다. 각 자리 숫자를 문자열 덧셈식으로 더하기 때문이다. 따라서 먼저 n개로 만들 수 있는 한자리 수가 있다면 그것이 minDP 배열값이 될 것이고, n개로 만들 수 있는 한 자리수가 없다면 2자리로 늘린다. 마찬가지로 2자리에서도 더이상 만들 수 있는 한자리가 없다면 3자리로,.. 이런 식으로 반복한다.
성냥 갯수 기준으로 다시 표를 작성해보면, 성냥갯수 n으로 만들 수 있는 한자리 수의 최솟값과 최댓값을 구할 수 있다.
성냥갯수가 7개까지 한자리수로 나타낼 수 있고, 8개부터는 2자리 수로 쪼개야한다. 성냥갯수는 최소 2개부터 시작하기 때문에 n=8이라고 하면 2자리로 된 수 (2,6) (3,5) (4,4) (5,3) (6,2) 5가지 경우의 수 중에서 각 자릿수 를 문자열 덧셈했을 때 최솟값이 minDP[8]의 배열값이 된다.=>"초기 조건"을 7이 아니라 8까지 해야 답이 나온다(?) 7로 해서 답이 나오지 않는다면 초기 조건을 변경해봐야한다고 한다.
minDP[8] = minDP[2]+minDP[6] 일때, 최솟값 10진수를 만든다. 최솟값 만들 때, 유의할 것은, 예를 들어 minDP[11]을 구하려고 할 때, (2,9)에서 더 쪼개질 수 있다. (2,2,7) 이런식으로. 하지만 이렇게 하면 3자리수가 되버리기 때문에 문제에서 요구한 대로 숫자 자체가 작아야하기 때문에 자릿수가 늘어나는 것보다 (4,7) 처럼 자릿수를 늘이지 않고, 최대한 2자리수로 유지해야한다. 따라서 배열값이 아무리 커봤잦 자릿수가 늘어나지 않을 수 있으면 그것이 그 자체로 최솟값을 만들어낼 수 있다!
minDP[11] = minDP[2] + minDP[2] + minDP[7]=117 > minDP[5] + minDP[6] = 20
이전의 dp값과 초기 조건에 대한 새로운 배열?을 활용해서 dp값을 찾는다.
최댓값을 만들 때는, 최대한 자릿수를 늘려야한다! 배열값이 작더라도 자릿수가 늘 수 있다면 그 자체로 최댓값을 만들 수 있기 때문이다! n이 짝수라면, 최댓값은 성냥개비 2개로 n/2개 늘이면 최다 자릿수가 될 수 있다. n이 홀수라면 성냥개비 2개와 3개로 홀수를 만들어낼 수 있기 때문에 3 + 나머지는 1로 채우는 식으로 규칙성을 발견해낼 수 있다. (2개로 최대한 자릿수 늘이고, 나머지 홀수갯수 3개로 만드는 최댓값 7을 맨 앞자리에 둔다.) =>한 자릿수당 최소 갯수로 최다 자릿수 만들어내면 된다!!!
n이 홀/짝인지에 따라 만들 수 있는 최댓값을 정리해보면 ① n=짝수 : 1이 n/2개 ② n=홀수 : 7 + 1이 (n/2)-1개
10진수
1
2
3
4
5
6
7
8
9
0
성냥갯수
2
5
5
4
5
6
3
7
6
6
성냥갯수
2
3
4
5
6
7
10진수
1
7
4
2,3,5
0,6
8
최솟값⭐️
1
7
4
2
0
8
최댓값
1
7
4
5
6
8
성냥갯수
8
9
10
11
12
13
14
15
최솟값
10
18
22
20
최댓값
1111
7111
11111
71111
111111
711111
1111111
111111