[코테/백준] Python 기타줄 - 1049번

실패 | 시도 - 번

 

🔗 [백준] 1049번 기타줄

1049 : [그리디 알고리즘] 기타줄(py)

---

문제 설명

Day Of Mourning의 기타리스트 강토가 사용하는 기타에서 N개의 줄이 끊어졌다. 따라서 새로운 줄을 사거나 교체해야 한다. 강토는 되도록이면 돈을 적게 쓰려고 한다. 6줄 패키지를 살 수도 있고, 1개 또는 그 이상의 줄을 낱개로 살 수도 있다.

끊어진 기타줄의 개수 N과 기타줄 브랜드 M개가 주어지고, 각각의 브랜드에서 파는 기타줄 6개가 들어있는 패키지의 가격, 낱개로 살 때의 가격이 주어질 때, 적어도 N개를 사기 위해 필요한 돈의 수를 최소로 하는 프로그램을 작성하시오.

---

문제 분석

돈을 적게 쓰는 것이 목표이기 때문에 개수를 정확히 맞출 필요없이 돈이 적게 나올 수 있게 한다. 

 

예제 입력 1 

줄 : 4개

패키지 : 12 (낱개 : 2) / 낱개 : 3

패키지 : 15 (낱개 : 2.x) / 낱개 : 4

→ 낱개당 가격으로 따졌을때 금액이 12인 패키지를 사는 것이 낫다.

 

예제 입력 2

줄 : 10개

패키지 : 20 (낱개 : 3.x) / 낱개 : 8

패키지 : 40 (낱개 : 6.x) / 낱개 : 7

패키지 : 60 (낱개 : 10) / 낱개 : 4

→ 낱개당 가격으로 따졌을때 금액이 20인 패키지를 사는 것이 낫다. 20인 패키지 1개를 사고 나머지 줄 4개에 대해서는 패키지를 사는게 나은지, 낱개로 사는게 나은지 가격비교를 해야한다. 20인 패키지를 1개 더 사게 되면 20 금액이 들고 금액이 4인 낱개로 구매하면 4 * 4 = 16 금액이 든다. 낱개로 사는 것이 더 낫기 때문에 20 * 1 + 4 * 4 = 36이 된다. 

---

정리

1. 패키지 가격과 낱개 가격을 비교한다.

• 패키지 가격 vs 낱개 6개 가격

 

2. 패키지 가격이 더 싸다면 살 수 있는 패키지 개수만큼 산다.

• 줄 개수(N) // 6

2-1. 패키지 개수만큼 산 후, 나머지 줄의 개수는 세트 1개를 더 사는게 나은지, 낱개로 사는게 나은지 비교한다.

• 나머지 줄 가격 : 패키지 가격 vs 줄 개수(N) % 6 * 낱개 가격 

 

3. 낱개 가격이 더 싸다면 줄 개수만큼 산다. 

• 낱개 가격 * 줄 개수(N)

---

입력

첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주어진다. 가격은 0보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

---

출력

첫째 줄에 기타줄을 적어도 N개 사기 위해 필요한 돈의 최솟값을 출력한다.

---

입력과 출력 예시

입력	출력
4 2 12 3 15 4	12
10 3 20 8 40 7 60 4	36
15 1 100 40	300
17 1 12 3	36
7 2 10 3 12 2	12
9 16 21 25 77 23 23 88 95 43 96 19 59 36 80 13 51 24 15 8 25 61 21 22 3 9 68 68 67 100 83 98 96 57	6

---

Trial 1

처음에는 N이 6 이하인지, 초과인지를 기준으로 조건문을 작성하였다. 그 때의 생각으로는 6 이하인 경우는 (N % 6) * 낱개 금액과 패키지 가격을 비교하고 6을 초과하는 경우에는 6을 나눈 몫과 나머지를 구해 낱개와 패키지 금액을 비교하려고 했다. 또 6 이하인 경우에서 패키지의 낱개당 가격을 구하기 위해 float 형태로 나타내려고 했다. 

→ 굳이 N을 6 기준으로 조건을 나눌 필요가 없었다. 어차피 아래 식에서 몫이 0이면 line_thing * min_line_set는 0이 되고 min() 함수에서 저렴한 가격을 고르기 때문이다.

result = line_thing * min_line_set + min(min_line_set, line_rest * min_line_single)

→ float 형태를 사용하지 않는게 낫다고 생각한다. 처음에 line_set 리스트에 패키지의 낱개 가격을 float으로 넣었는데 나중에 계산할 때 번거로운 일이 발생했다. 그래서 차라리 낱개 가격 * 6으로 계산해서 비교하는 것이 더 나은 방법이라는 것을 알게 되었다.

if min_line_set <= min_line_single * 6:

 

Trial 2

다른 분들의 코드를 보고 if문을 min() 함수로 간단히 표현하는 것을 참고하여 if문을 min()으로 수정하였다.

---

내 소스

• 첫시도 : 실패 (구현 실패)

N, M = map(int, input().split())
line_set = []
line_single = []
for _ in range(M):
    six_line, single_line = map(int, input().split())
    line_set.append(six_line)
    line_single.append(single_line)

min_line_set = min(line_set)
min_line_single = min(line_single)

line_thing = N // 6
line_rest = N % 6
if min_line_set <= min_line_single * 6:
    result = line_thing * min_line_set + min(min_line_set, line_rest * min_line_single)
else:
    result = min_line_single * N
print(result)

 

소스 설명

N, M = map(int, input().split())
line_set = []
line_single = []
for _ in range(M):
    six_line, single_line = map(int, input().split())
    line_set.append(six_line)
    line_single.append(single_line)

[1 - 7]

- 기타줄의 개수(N)와 브랜드 종류(M)를 입력받는다.   

- line_set, line_single 리스트는 각각 패키지 가격과 낱개 가격을 담기 위한 리스트이다.

- 브랜드 종류만큼 for문을 돌린다. 패키지 가격과 낱개 가격을 입력받아 각 리스트에 추가해준다.

 

min_line_set = min(line_set)
min_line_single = min(line_single)

[9 - 10] : 제일 중요한 것은 가장 낮은 가격이기 때문에 min() 함수를 사용해서 가장 작은 금액을 구하고 min_line_set, min_line_single 변수에 저장한다.

 

line_thing = N // 6
line_rest = N % 6
if min_line_set <= min_line_single * 6:
    result = line_thing * min_line_set + min(min_line_set, line_rest * min_line_single)
else:
    result = min_line_single * N

[12 - 17]

- 6으로 나눈 몫과 나머지를 구한다.

- 패키지와 낱개의 가격을 비교하기 위해 패키지 1개와 낱개 6개의 가격을 비교한다. 

- 만약 패키지 가격이 더 싸다면 6으로 나눈 몫 * 패키지 가격 + 나머지 줄 가격을 result 변수에 저장한다.

• 패키지를 구매하고 나머지 줄에 대해서 패키지 가격이 나은지, 낱개 가격이 나은지 비교해야 한다. min() 함수를 사용해서 줄 가격을 계산한다. → min(패키지 1개 가격,  6으로 나눈 나머지 * 낱개 가격)

- 패키지보다 낱개 가격이 더 싸다면 낱개 가격 * 줄 개수(N)를 계산한다. 

---

다른 코드 분석

- [1] 작성자분은 리스트에 튜플(패키지 가격, 낱개 가격)을 넣어 계산하셨다. 튜플을 패키지, 낱개 기준으로 오름차순 정렬을 하였다.  

- [6] 작성자분은 while 문을 사용하여 줄의 개수(N)가 0이상일 때만 반복하게끔 코드를 짜셨다. 

- 코드 작성의 차이만 있을 뿐 다들 같은 접근법으로 풀었다. 

---

회고

- 문제를 풀 때 쉽다고 느껴져서 당연히 금방 맞힐 줄 알았다. 테스트 케이스도 다 통과하고 질문 게시판에 있는 반례도 찾아서 입력했을 때 다 통과하였다. 그런데 계속 틀렸다고 나와서 오랫동안 붙잡고 있다가 결국 풀었다. 문제를 풀고나니 뿌듯하기 보단 현타가 왔다... 아직까지도 내 소스가 어떤 것이 문제였는지 모르겠다. 일단 소스가 간결하지 않고 길어서 다시 검토를 하려는 것이 좀 두렵다. 

백준 1049번 삽질 기록

---

Ref. 

1. 문제 풀이 / https://yoonsang-it.tistory.com/45

2. 문제 풀이 / https://wonyoung2257.tistory.com/64

3. 문제 풀이 / https://jie0025.tistory.com/161

4. 문제 풀이 / https://my-coding-notes.tistory.com/361

5. 문제 풀이 / https://afterdawncoding.tistory.com/196?category=998515

6. 문제 풀이 / https://velog.io/@devheyrin/%EB%B0%B1%EC%A4%80-%ED%8C%8C%EC%9D%B4%EC%8D%AC-1049-%EA%B8%B0%ED%83%80%EC%A4%84

---

* 잘못된 부분에 대해 댓글 남겨주시면 감사하겠습니다! 😀