문제
상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.
상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.
상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)
출력
상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.
풀이
나에게는 백준과 알고리즘, 기타 문법 등... 을 수련하도록 이끌어주신 스승이 있다.
스승님 가라사대... 골드 전까지는 30분 고민해보고 안 풀리거든 그냥 검색해서 공부해라 하셨거늘
어리석은 제자가 홀로 수련하다 보니 한 시간이 꼬박 걸려버리고 말았다. (결국 구글링했다.)
나의 풀이 (실패)
아래와 같이 케이스를 구분했다.
3 또는 5의 배수인 경우:
1. N이 5의 배수인 경우
2. 3의 배수인 경우
2-1. 3의 배수이면서 15보다 큰 경우
2-2. 3의 배수이면서 15보다 작은 경우
else:
1. 3의 배수와 5의 배수의 합으로 표현할 수 있는 경우
2. else: (표현할 수 없음)
이렇게 구분한 이유:
처음 코드를 짤 때, 5의 배수와 3의 배수를 생각했다.
(당연히) 오류가 났고, 수정하는 과정에서 12와 18이 서로 다른 케이스라는 걸 알았다.
12의 최적해는 3x4, 즉 4이고, 18의 최적해는 3x6의 6이 아닌 5x3 + 3x1의 4 (3+1)이다.
15보다 큰 3의 배수는, 5에 곱하는 수가 최대의 3의 배수일 때 최적해가 된다.
- 이 코드 제출할 때 3의 배수이면서 15보다 큰 경우, 3의 배수와 5의 배수의 합으로 표현할 수 있는 경우에 같은 연산을 수행하고 있다는 걸 깨달아서 둘을 합쳤다.
코드
N = int(input())
N5 = N//5
N3 = N//3
if (N%5==0):
print(N5)
elif N%3 == 0 and N<15:
print(N3)
else:
for i in range(1,N5+1):
if(N-i*5)%3==0:
N5=i
N3=(N-N5*5)//3
print(N3+N5)
break
print(-1)사실 이 코드는 아주 작은 수 (1~20) 또는 아주 큰 수 (5000)에 대해서는 잘 굴러간다.
그래서... 테스트 케이스는 잘 되는데 뭐지... 하고 질문 게시판에서 반례를 찾다가, 32, 70, 34 같은 적당한 크기의 숫자들에는 모조리 오류가 있는 걸 알게 됐다.
조금 수정해서는 안 되는... 어떤 근본적인 오류가 있다고 생각되어 답을 구글링했다.
구글링해서 찾은 풀이 (정답)
케이스는 아래 네 가지로 나누어진다.
- 5의 배수
- 5x + 3y
- 3의 배수
- 위 세 가지에 속하지 않음 (print(-1))
N = int(input())
cnt = 0
if(N % 5 ==0): #만약 5의 배수이면, 5로 나눈 몫을 출력한다.
print(int(N//5))
else:
while (N>0):
cnt += 1
N -= 3
if(N%5==0): #주어진 값-3이 5의 배수이면, 5로 나눈 몫 + cnt (3을 뺀 횟수)를 더해 출력한다.
print(int(N/5) + cnt)
break
elif(N == 1): # 주어진 값=3y+1이면, 5x+3y 조합으로 나타낼 수 없다.
print(-1)
break
elif(N==0): # 주어진 값이 3의 배수일 때: 3으로 나눈 몫을 출력한다.
print(int(N//3))
break
사람들은 정말 똑똑한 것 같다....
원래 찾은 풀이에는 while 문 속에 있는 두 번째 elif(N==1)이 아니라 elif(N==1 or N==2)였는데, 이해하느라 쳐다보는 동안 N==2인 케이스는 없다는 것을 알게 돼서 수정했다.
- N=2라면, 직전 iteration에는 N=5였을 것이다. 그러면 바로 위에 있는 if문에 걸려서 loop가 끝났어야 한다.
반성
- 쉬운 문제 (동전 거슬러주기) 라고 생각해서 깊게 고민하지 않고 풀려고 했던 게 큰 패인인 것 같다.
- 그리디 알고리즘 문제 중 작은 문제가 큰 문제에 포함되지 않는 케이스... 인데 너무 섣불리 접근한 듯함.
- 문제를 천천히 읽자....
- 케이스를 나눌 때, 문제의 골자를 잘 이해하고 나눴어야 하는데, 테스트 케이스만 보고 케이스를 나누려고 해서 케이스가 너무 복잡해졌다.
- 내가 나눈 케이스는 너무 복잡해서 MECE에 부합하는지도 판단하기 어렵다.
⇒ 이 다음 문제부터는 (1) 문제를 충분히 천천히 읽고 (2) 문제의 구조를 파악하고 (그림을 그리든 말로 풀어 쓰든) (3) 풀이를 충분히 생각한 뒤 문제에 접근해야겠다.
