탐욕법. [1789, 10162, 10610]

[1. 문제 설명]

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

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

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

---

[2. 풀이 접근]

=== 문제 10162 ===

이 문제는 아래 링크에서 5585 와 비슷한 방식으로 접근하면 된다.

버튼을 최소한으로 눌러야 하므로, 동작 시간이 긴 전자레인지를 최대한 많이 사용하는 것이다.

• https://testkernelv2.tistory.com/525

---

=== 문제 1789 ===

서로 다른 자연수를 최대한 많이 사용하려면, 가장 작은 자연수부터 사용하면 된다.

1 부터 계속 더해나가다가, 그 합이 S 이상이 된 경우를 멈춘다.

이 때 두가지 경우가 있다.

1. 그 합이 정확히 S 인 경우,
   => 지금까지 사용한 자연수 개수가 답이 된다.
   
   
2. 그 합이 S 를 초과하는 경우,
   => 이번에 더한 자연수로 인해 합이 S 를 초과하였으므로
   => 바로 이전까지 사용한 자연수 개수가 답이된다.
   => 만약, 자연수들을 출력해야 한다면
   => 초과하기전 합과 S 의 차이를 구한 뒤, 이 차이(diff) 를 가장 마지막에 더한 자연수에 더해주면 된다.
   => 1 ~ K 까지는 서로 겹치지 않는다. 
   => 따라서 (K + diff) 역시 1 ~ (K-1) 과 겹치지 않는다.

---

=== 문제 10610 ===

30은  2*5*3 이므로, 30의 배수는 2의 배수이면서, 5의 배수이기도 하고 3의 배수가 되기도 한다. 

2*5 는 10이므로 10의 배수는 항상 0으로 끝나야 한다.

• 입력으로 받는 숫자에서 0 이 없으면, 30의 배수를 만들 수 없다.

3 의 배수는 그 숫자들의 합이 항상 3의 배수가 된다.

• 111 의 각 자리의 합이 3 이며, 3으로 나누어 떨어진다.
• 즉, 입력으로 받는 숫자에서 0을 제외한 각 자리의 합이 3의 배수가 아니면, 30의 배수를 만들 수 없게 된다.

위 두가지 경우를 모두 만족하면, 어떻게 배치해도 30의 배수를 만들 수 있다.

문제에서 원하는 값은 가장 큰 30의 배수이므로, 큰 값이 가장 큰 자리수에 와야 한다.

• 탐욕법을 적용하여, 큰 값이 가장 큰 자리수에 오도록 코드를 작성한다.

주의사항

• 입력으로 주어지는 숫자의 길이는 100,000 이다.
  => 정수형 범위의 데이터가 아니다.
• 문자열로 입력을 받아야한다.

---

[3. 코드 - 10162]

---

[3. 코드 - 1789]

---

[3. 코드 - 10610]