문제
3개의 시간조절용 버튼 A B C가 달린 전자레인지가 있다. 각 버튼마다 일정한 시간이 지정되어 있어 해당 버튼을 한번 누를 때마다 그 시간이 동작시간에 더해진다. 버튼 A, B, C에 지정된 시간은 각각 5분, 1분, 10초이다.
냉동음식마다 전자레인지로 요리해야할 시간 T가 초단위로 표시되어 있다. 우리는 A, B, C 3개의 버튼을 적절히 눌러서 그 시간의 합이 정확히 T초가 되도록 해야 한다. 단 버튼 A, B, C를 누른 횟수의 합은 항상 최소가 되어야 한다. 이것을 최소버튼 조작이라고 한다.
만일 요리시간이 100초라고 하면(T=100) B를 1번, C는 4번 누르면 된다. 이와 다르게 C를 10번 눌러도 100초가 되지만 이 경우 10번은 최소 횟수가 아니기 때문이 답이 될 수 없다. 이 경우 B 1번, C 4번, 총 5번이 최소버튼 조작이다. 그리고 T=234와 같이 3개의 버튼으로 시간을 정확히 맞출 수 없는 경우도 있다.
여러분은 주어진 요리시간 T초를 맞추기 위한 최소버튼 조작 방법을 구하는 프로그램을 작성해야 한다.
입력
첫 번째 줄에는 요리시간 T(초)가 정수로 주어져 있으며 그 범위는 1 ≤ T ≤ 10,000 이다.
그냥 Greedy algorithm으로 풀어. 이런 건. 동전 거슬러주기 문제라던가 이런 문제는 그리디로 풀면 쉽게 풀림. 물론 높은 단위가 낮은 단위의 배수가 되지 않는 경우라면 그리디로 풀면 좆되지만 이런 건 그리디로 껌으로 풀린다.
빽준이 사이트 문제임?
네 .. ㅜㅜ 근데 제가 지금 C언어 초급이하수준이라서 많은문제풀고있는데 접근을 어캐해야할지... Greedy 가 먼말인지도 ...
큰 단위부터 계산해 나가라는 말임. 100초면 5분(300초)로 먼저 나눠보고, 그 다음 1분(60초)로 나눠보고, 그 다음 10초로 나눠보라는 말임.
Greedy algorithm의 한글 번역이 욕심쟁이 알고리즘임.
예를들어서 100초면 60으로 나누고 그 나머지를 10으로 또나눠서 몇번했는지 구하면되겟네요 ?
음. 그렇지. 가령 100초라고 하면, 300초 단위: 100 / 300 == 0, 60초 단위: (100 % 300) / 60 == 1, 10초 단위: ((100 % 300) % 60) / 10 == 4, 1초 단위: (((100 % 300) % 60) % 10 == 0이 되는데, 1초 단위가 1이라도 있으면 그건 못 푸는 경우이고, 아니라면 300초 단위, 60초 단위, 10초 단위 출력해 주면 됨.
근데 300은 60으로 나누어 떨어지고 60은 10으로 나누어 떨어지니까 (100 % 300) % 60 은 100 % 60으로, ((100 % 300) % 60) % 10 은 100 % 10으로 간단히 쓸 수 있어.
http://dblack.tk
커뮤니티 사이트 입니다 많은 이용 부탁 드립니다.