실패 | 시도 - 번
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이상일 때만 반복하게끔 코드를 짜셨다.
- 코드 작성의 차이만 있을 뿐 다들 같은 접근법으로 풀었다.
회고
- 문제를 풀 때 쉽다고 느껴져서 당연히 금방 맞힐 줄 알았다. 테스트 케이스도 다 통과하고 질문 게시판에 있는 반례도 찾아서 입력했을 때 다 통과하였다. 그런데 계속 틀렸다고 나와서 오랫동안 붙잡고 있다가 결국 풀었다. 문제를 풀고나니 뿌듯하기 보단 현타가 왔다... 아직까지도 내 소스가 어떤 것이 문제였는지 모르겠다. 일단 소스가 간결하지 않고 길어서 다시 검토를 하려는 것이 좀 두렵다.
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
* 잘못된 부분에 대해 댓글 남겨주시면 감사하겠습니다! 😀
'코딩테스트' 카테고리의 다른 글
| [코테/백준] Python 회의실 배정 - 1931번 (실패) (0) | 2023.01.31 |
|---|---|
| [코딩테스트] 백준 문제 풀고 자동으로 깃허브 커밋하기 (0) | 2023.01.29 |
| [코테/백준] Python 캠핑 - 4796번 (0) | 2023.01.27 |
| [코테/백준] Python 수 묶기 - 1744번 (0) | 2023.01.27 |
| [코테/백준] 레벨 기록 (0) | 2023.01.27 |
실패 | 시도 - 번
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이상일 때만 반복하게끔 코드를 짜셨다.
- 코드 작성의 차이만 있을 뿐 다들 같은 접근법으로 풀었다.
회고
- 문제를 풀 때 쉽다고 느껴져서 당연히 금방 맞힐 줄 알았다. 테스트 케이스도 다 통과하고 질문 게시판에 있는 반례도 찾아서 입력했을 때 다 통과하였다. 그런데 계속 틀렸다고 나와서 오랫동안 붙잡고 있다가 결국 풀었다. 문제를 풀고나니 뿌듯하기 보단 현타가 왔다... 아직까지도 내 소스가 어떤 것이 문제였는지 모르겠다. 일단 소스가 간결하지 않고 길어서 다시 검토를 하려는 것이 좀 두렵다.
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
* 잘못된 부분에 대해 댓글 남겨주시면 감사하겠습니다! 😀
'코딩테스트' 카테고리의 다른 글
| [코테/백준] Python 회의실 배정 - 1931번 (실패) (0) | 2023.01.31 |
|---|---|
| [코딩테스트] 백준 문제 풀고 자동으로 깃허브 커밋하기 (0) | 2023.01.29 |
| [코테/백준] Python 캠핑 - 4796번 (0) | 2023.01.27 |
| [코테/백준] Python 수 묶기 - 1744번 (0) | 2023.01.27 |
| [코테/백준] 레벨 기록 (0) | 2023.01.27 |
