[백준] 1082 방 번호

 

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

 

 

방 번호 

문제

 

스타트링크가 입주한 사무실은 방 번호를 직접 정할 수 있다. 방 번호를 정하려면 1층 문방구에서 파는 숫자를 구매해야 한다. 숫자를 구매하기 위해 준비한 금액은 M원이다.

문방구에서 파는 숫자는 0부터 N-1까지이고, 각 숫자 i의 가격은 Pi이다. 문방구에서는 같은 숫자를 여러 개 구매할 수 있고, 문방구는 매우 많은 재고를 보유하고 있기 때문에, 항상 원하는 만큼 숫자를 구매할 수 있다. 방 번호가 0이 아니라면 0으로 시작할 수 없다.

예를 들어, N = 3, M = 21, P0 = 6, P1 = 7, P2 = 8이라면, 만들 수 있는 가장 큰 방 번호는 210이다. 최대 M원을 사용해서 만들 수 있는 가장 큰 방 번호를 구해보자.

입력

첫째 줄에 N이 주아진다. 둘째 줄에는 공백으로 구분된 P0, ..., PN-1이 주어진다. 마지막 줄에는 M이 주어진다.

출력

첫째 줄에 최대 M원을 사용해서 만들 수 있는 가장 큰 방 번호를 출력한다. 적어도 하나의 숫자를 살 수 있는 입력만 주어진다.

제한

• 1 ≤ N ≤ 10
• 1 ≤ Pi ≤ 50
• 1 ≤ M ≤ 50
• N, Pi, M은 정수

예제 입력 1 복사

3
6 7 8
21

예제 출력 1 복사

210

예제 입력 2 복사

3
5 23 24
30

예제 출력 2 복사

20

 

 

풀이 아이디어

브루트 포스로 풀기에는 10^50임으로

그리디하게 접근했다. 

 

숫자를 구매해서 가장 높은숫자를 만드면 되는 문제로

가장 낮은 가격의 값으로 자릿 수를 채워보고

가장 높은 자리부터 높은 숫자로 바꿔가면 된다,

 

 

시행착오

앞자리가 0이 올 수 없는 점 때문에

 

3

5 23 24

30 

답 20

 

과 같은 문제에 대해서

00에서 자릿수 추가를 멈추고 높은 숫자로 바꾸는 방법을 택했으나

이 과정에서 하드 코딩이 들어가서인지

반례를 찾지 못한 채 코드를 버려야 했다.

 

결국 다른 사람의 풀이를 참고한 결과

00000으로 자릿수부터 만들고 

앞자리에 0대신 다른 숫자가 올 수 있을 때까지 푸는 아이디어를

가져왔고 풀 수 있었다.

 

최적화 해보기

만약 가격의 범위와 자릿수의 범위가 int이고

데이터 케이스가 자릿수 + (임의의 수)^(해당숫자) 이런식으로 들어온다면?

 

그리드로 풀었을 때 본 문제는 자릿수 * 10의 시간복잡도를 갖는다.

 

첫번째로 떠올린 최적화

숫자의 가격이 주어질 때 

가격이 오름차순으로 되는 수열만 계산하면 탐색 범위를 줄일 수 있다.

 

즉 

0이 10원이고 9가 1원이면 

9보다 작은 숫자이면서 9와 같거나 비싼 숫자는 전부 버리면된다.

 

다만 데이터 케이스가 오른차 순으로 들어올 수 있으므로

항상 최적화를 보장하진 않는다.

 

 

두번때로 떠올린 최적화

최악의 데이터 케이스인 오른차순이라 가정한다면. 

0~9까지중 구매 가능한 숫자를 이분 탐색으로 결정해서 구매할 수 있다.

 

그럴 경우

자릿수 ^ log₂ 10 으로 해결 가능하다.