문제 풀이
그리디
버튼 증감을 반대로 생각하고 N을 0으로 만드는 횟수를 다음과 같이 구함
-
N을 10으로 나눈 나머지가 5라면 N을 60으로 나눈 나머지가 40이 넘는지 확인함
-
이때 40을 넘는다면 10으로 나눈 나머지가 0이 되도록 1씩 더하고 아니라면 나머지가 0이 되도록 1씩 빼고 버튼 횟수 추가
-
N을 10으로 나눈 나머지가 5를 넘는다면 나머지가 0이 되도록 1씩 더하고 버튼 횟수 추가
-
N을 10으로 나눈 나머지가 5보다 작다면 나머지가 0이 되도록 1씩 빼고 버튼 횟수 추가
-
N을 60으로 나눈 나머지가 30보다 크다면 나머지가 0이 되도록 10씩 더하고 버튼 횟수 추가
-
N을 60으로 나눈 나머지가 30보다 작거나 같다면 나머지가 0이 되도록 10씩 빼고 버튼 횟수 추가
-
N을 60으로 나눈 몫만큼 60씩 감소시키는 버튼 횟수 추가
저장된 버튼 횟수 출력하면 정답
풀이 설명
버튼의 동작이 각각 60 증가, 10 증가, 10 감소, 1 증가, 1 감소이고 0에서 특정 값 N까지 값을 증가시켜야 하기 때문에 작은 단위의 버튼보다는 큰 단위의 버튼을 누르는 것이 눌러야 하는 버튼의 횟수를 줄이는 것이다.
그러므로 먼저 최대한 60 증가시키는 버튼을 많이 누르기 위해 N을 60으로 나눈 몫만큼 증가 버튼을 누르면 60으로 나눈 나머지를 0에서 버튼을 최소 횟수로 눌러서 만드는 문제가 된다. 그리고 이때 값을 만들기 위해 60을 증가시키고 작은 단위로 빼서 만드는 방법과 그냥 작은 단위로 증가만 시켜서 만드는 방법이 나뉘게 된다. 그리고 이는 구하는 나머지 값이 0에 가까우면 증가시키는 경우가, 60에 가까우면 60을 증가시킨 후 감소시키는 방법이 버튼 누르는 횟수가 적게 된다.
즉, 나머지가 단위의 절반보다 큰지 작은지에 따라 효율적인 방법이 나온다는 것이다. 다만 여기서 주의해야 할 점은 최소 횟수로 누르는 방법이 여러가지인 경우에는 사전 순으로 가장 앞서는 방법을 출력해야 한다는 것이다. 이는 버튼의 순서가 증가시키는 버튼이 먼저 앞으로 오기 때문에 앞의 버튼의 횟수가 적은 것이 사전 순으로 앞선다는 것은 즉 같은 방법이면 최대한 증가 버튼을 덜 누르는 방법으로 해야 한다는 것이다.
하지만 보통의 경우라면 단위의 절반을 만들기 위해 더 큰 단위에서 감소시키는 버튼의 횟수가 증가시키는 버튼의 횟수보다 많기 때문에 신경쓸 필요가 없는 조건이지만 60으로 나눈 나머지가 45 이상이고 그 나머지를 10으로 나눈 나머지가 5일때는 얘기가 달라진다. 이 때는 1을 증가시키고 10을 증가시켜서 만드는 방법보다 60에서 10을 감소시키고 1을 감소시키는 경우가 더 버튼을 적게 누르기 때문이다.
다시 말해 10의 단위에서 나머지가 절반이고 60의 단위의 나머지가 절반이 넘는 경우일 때 즉, 현재 단위에서 절반이고 더 큰 단위에서 절반이 넘을때는 더 큰 단위에서 감소시켜 만드는 것이 더 빠르거나 사전 순으로 앞서는 경우가 생긴다.
따라서 N을 60으로 나눈 나머지를 앞서 설명한 것처럼 10으로 나눈 몫과 나머지를 이용해 10을 증가시키는 버튼과 1을 증가시키는 버튼만 사용하거나 또는 나머지를 60에서 10을 감소시키는 버튼과 1을 감소시키는 버튼만으로 만드는 상황을 비교해 버튼을 더 적게 누르는 상황을 생각하면 된다.
그러므로 설명한 바와 같이 60으로 나눈 몫과 나머지, 그 나머지를 10으로 나눈 몫과 나머지를 이용해 증가 버튼, 감소 버튼을 선택해 눌러서 횟수를 세고 출력하면 정답이 된다.
소스 코드
fun main(){
val T = readLine()!!.toInt()
repeat(T){
var N = readLine()!!.toInt()
val buttons = IntArray(5)
if(N % 10 == 5){
if(N % 60 > 40){
buttons[4] += 10 - (N % 10)
N += 10 - (N % 10)
} else {
buttons[3] += N % 10
N -= N % 10
}
} else if(N % 10 > 5){
buttons[4] += 10 - (N % 10)
N += 10 - (N % 10)
} else {
buttons[3] += N % 10
N -= N % 10
}
if(N % 60 > 30){
buttons[2] += (60 - (N % 60)) / 10
N += 60 - (N % 60)
} else {
buttons[1] += (N % 60) / 10
N -= N % 60
}
buttons[0] = N / 60
for(button in buttons){
print("$button ")
}
println()
}
}