728x90
반응형
문제 바로가기
문제:
영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만들어 보려고 한다.
- 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
- 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
- 화면에 있는 이모티콘 중 하나를 삭제한다.
모든 연산은 1초가 걸린다. 또, 클립보드에 이모티콘을 복사하면 이전에 클립보드에 있던 내용은 덮어쓰기가 된다. 클립보드가 비어있는 상태에는 붙여넣기를 할 수 없으며, 일부만 클립보드에 복사할 수는 없다. 또한, 클립보드에 있는 이모티콘 중 일부를 삭제할 수 없다. 화면에 이모티콘을 붙여넣기 하면, 클립보드에 있는 이모티콘의 개수가 화면에 추가된다. 영선이가 S개의 이모티콘을 화면에 만드는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.
입력:
첫째 줄에 S (2 ≤ S ≤ 1000) 가 주어진다. ㅍ
출력:
첫째 줄에 이모티콘을 S개 만들기 위해 필요한 시간의 최솟값을 출력한다.
풀이:
import sys
from collections import deque, defaultdict
s= int(input())
dic = defaultdict(int)
dic[(1,0)] = 0
Q = deque([(1,0)])
while Q :
# 스크린, 클립 뽑아줌
screen, clip = Q.popleft()
if screen == s:
print(dic[(screen,clip)])
break
# 3가지 경우
for d_screnn, d_clip in [(screen,screen),(screen+clip,clip),(screen-1,clip)]:
# 범위에 들어있을경우
if 0 <= screen <= 2000 and 0 <=clip <=2000:
if (d_screnn,d_clip) not in dic.keys():
dic[(d_screnn,d_clip)] = dic[(screen,clip)]+1
Q.append((d_screnn,d_clip))
from collections import deque
s = int(input())
dp = [[-1]*(1001) for _ in range(1001)]
dp[1][0] = 0
#화면의 이모티콘, 클립보드 이모티콘
q = deque([(1, 0)])
while q:
screen, clip = q.popleft()
if screen == s:
print(dp[s][clip])
break
if dp[screen][screen] == -1:
dp[screen][screen] = dp[screen][clip]+1
q.append((screen, screen))
if 2 <= screen+clip <= 1000 and dp[screen+clip][clip] == -1:
dp[screen+clip][clip] = dp[screen][clip]+1
q.append((screen+clip, clip))
if 2 <= screen-1 <= 1000 and dp[screen-1][clip] == -1:
dp[screen-1][clip] = dp[screen][clip]+1
q.append((screen-1, clip))
1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
3. 화면에 있는 이모티콘 중 하나를 삭제한다.
하나는 디폴트 딕으로 풀었다, 디폴트 딕으로 하면 장점은 딕 안에 안 들어있을때 처리르 안 해줘도 된다. 알아서 추가된다.
어떤 미친 고수의 코드
INF = 999999999999999999
s = int(input())
num = [i for i in range(1005)]
i=1
while i<=s:
j=2
num[i-1]=min(num[i-1], num[i]+1)
while i*j<1002:
num[i*j] = min(num[i*j], num[i]+j)
num[i*j-1] = min(num[i*j-1], num[i*j]+1)
j+=1
i+=1
print(num[s])처음엔 나도 1차원 dp로 해결하려 했지만 절대 안됐다.. 이사람 대단하다
반응형
댓글