백준 2839

✔️ 문제

문제 출처 : https://www.acmicpc.net/problem/2839

2839번: 설탕 배달

 

✔️ 첫 풀이

n = int(input())

x = n//3
y = n//5

vl = []

for i in range(x+1):
    for j in range(y+1):
        if 3*i + 5*j == n:
            vl.append(i+j)

if vl:
    print(min(vl))
else:
    print(-1)

처음에 3x+5y=n 이라는 방정식을 중점으로 생각했었습니다.

그래서 x가 될 수 있는 최대값을  n//3으로, y가 될 수 있는 값을 n//5로 봤습니다.

 

그 다음, 2중 반복문을 돌려 방정식에 일치하는 x,y가 있으면 리스트에 그 합을 추가합니다.

 

반복문이 끝난 후 리스트에 값이 존재한다면 그 중 최소값을, 리스트가 없다면 조건을 만족하는 값이 없다는 뜻이니 -1을 출력합니다.

 

그런데, 이렇게 할 경우 시간이 364ms가 나와 개선이 필요하다고 느꼈습니다.

 

✔️ 개선된 풀이

l = []
r = n//5

for i in range(r+1):
    x = (n - i*5)//3
    
    if 3*x + 5*i == n:
        l.append(x+i)
if l:
    print(min(l))
else:
    print(-1)

그래서 반복문을 한 번 돌릴 수 있는 방법을 생각하게 되었고, x값을 최소한으로 하고 y값을 최대한으로 하는 게 좋은 방법이라는 결론에 도달했습니다.

 

그 이유는 n=15일 때 가장 좋은 건 x=0, y=3이기 때문에 y값을 기준으로 하는 것이 더 좋은 방향이라고 생각했기 때문입니다.

 

위의 코드에선 r이라는 변수를 잡았는데, 가질 수 있는 최대값을 설정하기 위해 n//5를 했습니다.

 

그리고 r을 반복문 돌린다음, 그에 맞게 x의 최대값을 설정했습니다.

 

돌아가는 x값 중 방정식에 일치하는 게 있다면 리스트에 추가합니다.

 

모든 반복문이 끝났을 때, 리스트에 값이 존재하면 최소값을, 아니라면 -1을 출력합니다.

✔️ 다른 사람 풀이

풀고 다른 사람이 푼 걸 봤는데 아래처럼 이렇게 푸는 건 아직 제수준에선 생각하지 못 했고,

백준에서 "숏코딩은 재미로만 보는 것이 좋습니다. 알고리즘을 배울 때는 길이를 최대한으로 줄인 코드보다 자신이 알아보기 쉬운 코드가 우선입니다." 라고 하는 말에 공감했기 때문에 이렇게 풀 수 있구나 하고 넘어갔습니다.

n=int(input())
print(-(n in[4,7])or n-2*n//5*2)

 

그리고 while문에 대해 생각을 못 했어서 while로 푼 방법을 찾아봤는데

r=0

while n>=0:
    if n%5 == 0:
        r += n//5
        print(r)
        break
    n-=3
    r+=1

else:
    print(-1)

while로 풀 때도 5의 배수를 기준으로 값을 줄여나가는 걸 확인할 수 있었습니다.