[백준] 2839 설탕 배달 python 알고리즘 문제

 

문제 2839. 설탕 배달

 

1. 나의 코드와 발상 과정

n = int(input())
new_n1, new_n2 = n, n
cnt1, cnt2 = 0, 0

cnt1 += new_n1 // 5
new_n1 = new_n1 - cnt1 * 5
cnt1 += new_n1 // 3
if new_n1 % 3 != 0 :
    vari1 = -1
else :
    vari1 = cnt1

cnt2 += new_n2 // 3
new_n2 = new_n2 - cnt2 * 3
cnt2 += new_n2 // 5
if new_n2 % 5 != 0 :
    vari2 = -1
else :
    vari2 = cnt2

if vari1 == -1 :
    if vari2 > 0 :
        print(vari2)
    else :
        print(-1)
elif vari2 == -1 :
    if vari1 > 0 :
        print(vari1)
    else :
        print(-1)

그리디를 막 배운 상태였기 때문에,

(1) n을 5로 나눈 몫을 구한 다음, 그 (2) 나머지를 다시 3으로 나눈 몫을 구하고  (3) 자동으로 나머지가 생기면 -1을 출력하게 했다.

그러나 이 문제는 억지로라도 3킬로 봉지를 더 쓴다 하더라도 최대한 채우는 것을 목표로 한다.

 

그렇기에 나는 케이스를 크게 두 가지로 나누었다.

(1) 5를 먼저 나누고 그다음 3을 나눈 케이스와

(2) 3을 먼저 나누고 그 다음 5를 나눈 케이스를 비교하여

(3) 각각 나눈 횟수(=3과 5로 나눈 몫)를 cnt1, cnt2 변수에 담아

(4) 둘 중 더 작은 케이스를 선택하고,

(5) 만약 둘 다 -1 일 경우 최종적으로 -1을 출력하게 했다.

 

그러나 어떻게 해도 통과가 되지 않았다.

많은 반례들을 넣어 통과시켰는데도 어디서 인가 되지 않았다.

 

2. 고수님의 깔끔한 코딩

sugar = int(input())
count = 0

while True:
    if (sugar % 5) == 0:
        count = count + (sugar//5)
        print(count)
        break
    sugar = sugar - 3
    count += 1

    if sugar < 0:
        print("-1")
        break

????

5의 배수가 되면 무한 루프가 걸린 while문을 빠져나가게 하고,

그 전에는 sugar = sugar - 3으로 3을 빼고, 그 뒤에 count를 붙여 봉투의 수를 계산한다.

 

만약에 위의 두 가지의 방법으로 나누어 떨어지지 않으면

어떻게 해도 모든 봉투를 꽉 채울 수 없다. 당연히 sugar는 음수가 되며 break를 통해 나가게 된다.

 

결론적으로 계속 -3을 하면서 sugar를 5의 배수가 되게 만들어 탈출을 시도한 간결한 코드가 되었다.

 

큰 수를 먼저 활용하는 그리디의 풀이 방법에

while의 특성(반복 횟수를 모를 때 사용, break) -> 그리디 풀이 방법(가장 큰 수를 먼저 연산한다)

뭐 이런 식으로 접근하여 푼 것 같다.

 

3. 아쉬운 점

대체 어디가 틀린 지 아직도 모르겠다.

당연히 아래처럼 짰으면 반례가 생길 수가 없지 않았을까 하는 생각이.. 든다.

노가다 식이 아닌 발상을 잘 검증하고 코드를 써내려 가야겠다는 다짐을 해본다...

 

 

 

...

혹시 지나가시다가 코린이를 구해주실 고수님은

댓글로 제 코드의 오류를 부숴주시면 아주 감사하겠습니다.

 

 

끝!