설탕 배달

내가 작성한 코드 (Greedy방식)

N = int(input())
i = 0
while (N - (3 * i)) > 0 and (N - (3 * i)) % 5 != 0:
    i += 1
if N - (3 * i) < 0:
    print(-1)
else:
    print(int(((N - (3 * i)) / 5) + i))

고민한 부분

• 처음에 단순히 5로 나눈 나머지를 3으로 나누었을 때 떨어지는 경우를 생각했다.
  하지만, 4, 11, 17, 51 등 5의 개수와 3의 개수가 적절히 필요한 경우가 생겼다.

  해결방법
  받은 수 N을 5로 최대한 나누고 나누어지지 않을 때 3으로 나누어 떨어지는 경우를 구하기 위한 공식을 세웠다.
  (N - (3 * i)) % 5 != 0
  반복적으로 i을 올려가며 3의 비중을 올렸다.

• n - (3 * 1)이 음수가 나왔더라도 while문이 끝나지 않아 테스트가 오래걸리는 경우가 발생했다.
  ex. -2 % 5 = 3 의 결과가 나왔다. 즉, 딱 나누어 질때까지 while을 불필요하게 돌고있었다.

  해결방법
  해당 경우가 음수일 경우 while을 빠져 나가도록 조건을 걸어주었다

DP 방식으로 푼 블로그 글