Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
Tags
- opic
- 오픽공부법
- 안드로이드
- 오픽점수잘받는방법
- 이진탐색
- XML주석
- 디피
- 오픽
- fibo
- 바텀업
- dynamicProgramming
- English
- 주석
- ㅂ
- 이진탐색 #나무 자르기
- 영어회화
- 오픽노잼
- topdown
- 탑다운
- 오픽가격
- stack 스택
- 오픽노잼공부방법
- 메모이제이션
- XML
- 다이나믹프로그래밍
- dp
- 안드로이드주석
- 피보나치수열
- 영어말하기
Archives
RUBY
만들 수 없는 금액 본문
출처:: k 대회 기출
분류:: 그리디
1. 문제 이해 및 해결과정
1) 동전 오름차순 정렬 후 2) 모든 경우 다해보고 나온 sum을 set에 넣음 3) 1부터 차례대로 인덱스와 값이 다른 지점의 인덱스가 만들 수 없는 최소값이다 => n이 1000이므로 2^1000 이되어 시간초과가 날 수 밖에 없다. 2. 그리디 - 거스름돈 문제는 각 화폐 단위마다 무한 개의 동전이 존재한다고 가정했는데, 이 문제에서는 동전의 수가 한정적이라는 점이 다르다 - 동전을 화폐 단위 기준으로 정렬한 뒤에, 화폐 단위가 작은 동전부터 하나씩 확인하면서 target변수를 업데이트 하는 방법으로 최적의 해를 계산할 수 있다. ex) 1 2 3 8 네 개의 동전이 있다고 가정 1) 처음에는 금액 1을 만들 수 있는 지 확인하기 위해 target=1로 설정 2) target = 1을 만족하는 지 확인 , 화폐 1이 있다. 이어서 target을 1+1=2로 업데이트 한다 = 1까지의 모든 금액을 만들 수 있다 3) target=2를 만족하는지 확인한다. 화폐 2인 동전이 있다. 따라서 target은 2+2=4로 업데이트 한다 = 3까지의 모든 금액을 만들 수 있다 4) target=4를 만족하는지 확인, 화폐 단위가 3인 동전이 있다. target=4+3=7이 된다 =6까지의 모든 금액 만들 수 있음 5) target=7을 만족하는지 확인 , 화폐 8인 동전이 있다. 7을 만드는 방법이 없다. => 정답은 7 |
2. 풀이방법
3. 오답원인
1. 시간초과
#만들 수 없는 금액
#
'''
5
3 2 1 1 9
'''
import sys
sys.stdin = open("input.txt","r")
n=int(input())
coin=list(map(int,input().split()))
coin.sort()
tmp=set()
def DFS(i,sum):
tmp.add(sum)
if i==len(coin):
return
else:
DFS(i+1,coin[i]+sum)
DFS(i+1,sum)
DFS(0,0)
table=list(tmp)
for i in range(0,len(table)):
if i!=table[i]:
print(i)
break
- 리스트를 오름차순 정렬하기, 1부터 되는 값을 확인해보기 라는 아이디어는 생각했지만 더 이상의 아이디어가 떠오르지 않았다.
4. 알게된 점
set()은 요소에 직접 접근할 수 없다
=> set을 리스트로 바꾸어 해결하였다.
'PS > This' 카테고리의 다른 글
[이론] 이진탐색 / 파라메트릭서치 (0) | 2020.09.18 |
---|---|
[백준] 최종 순위 (0) | 2020.09.15 |
[카카오] 무지의 먹방 라이브 (0) | 2020.09.12 |
볼링공 고르기 (0) | 2020.09.12 |
[백준] 럭키 스트레이트 (0) | 2020.09.10 |