(JAVA) 백준 1082번 : 방 번호 --- [문자열, 그리디]

www.acmicpc.net/problem/1082

1082번: 방 번호

 

안녕하세요.

 

문자열 문제인줄 알고 접근했는데 그리디였던 문제입니다.

 

 

해당 문제의 그리디 접근 방식은 간단합니다.

 

 

 

매커니즘

---

  1)  가장 최소비용으로 살 수 있는 숫자와 최소 비용을 별도로 저장합니다.

  

  2)  가장 최소비용으로 살 수 있는 숫자의 최대 개수를 구합니다.

 

  3)  가장 최소비용으로 살 수 있는 숫자가 0인지 아닌지 체크합니다. (0만 다사면은 숫자가 성립되지 않으므로)

  *** 가장 최소비용으로 살 수 있는 숫자를 최소숫자라고 하겠습니다.  

 

  3-1)  0만 전부 산 경우

    ->  하나의 최소숫자를 팔아서 그 가격만큼 돈을 확보한 후, 0을 제외한 숫자 중 가장 큰 숫자부터 하나씩 살 수 있는지 탐색합니다.

    ->  탐색 결과 하나를 구매했다면, 혹시 하나를 더 팔아서 다른 숫자를 살 수 있는지 3-1) 처음부터 진행하며 더이상 숫자를 살 수 없을때까지 이를 반복합니다.

    ->  만약 아무것도 살 수 없는 경우 하나를 더 팔아서 다른 숫자를 사는 것 보다 판 숫자를 다시 가져와서 만드는게 더 큰 숫자가 되므로 갯수만큼 최소숫자를 뒤에 이어붙이고 종료합니다.

    ->  단, 전부 0인 상태에서 아무것도 살 수 없는 경우 0으로 이루어진 숫자는 존재할 수 없기 때문에 무조건 몇 개를 팔아서라도 0이 아닌 숫자를 사야합니다.

 

  3-2)  0이 아닌 숫자를 전부 산 경우

    ->  3-1) 과 동일하게 진행합니다. 대신, 반복문 종료 후 0이 아닌 최소숫자를 개수만큼 뒤에 이어붙입니다.

 

 

 

이상입니다.

 

감사합니다.

 

소스코드

---