https://www.acmicpc.net/problem/14226
14226번: 이모티콘영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만www.acmicpc.net
거의 정답보고풀었다.
주의할점은 , 개수만 생각하면 안된다는 것이다.
백준 질문계시판에서 본 글인데, 우리가 임의의 숫자까지 갈 수 있는 최적의 경로가, 정답까지의 최적의 경로라고는 할 수 없다.https://www.acmicpc.net/board/view/30100
보고 머리가 띵했다.
먼져 2차원배열의방식이 있다.
dp[i][j]=i를만들때 클립보드가 j인 경우까지 드는 최소시간을 뜻한다.
3가지 경우로 bfs를 진행하면 된다.
#코드
import sysinput=sys.stdin.readlinefrom collections import dequen=int(input())
#dp=[i][j]=i를만들었을때, 클립보드가j일때의 횟수dp=[[-1 for _ in range(n*2)]for _ in range(n*2)]
que=deque()que.append((1,0))dp[1][0]=0while que: tmp,clip=que.popleft()
value=dp[tmp][clip] if tmp==n: print(value) exit()
#1개 삭제하는 경우 if tmp>0 and dp[tmp-1][clip]==-1:
dp[tmp-1][clip]=value+1 que.append((tmp-1,clip))
#클립보드에 복사하는 경우 if dp[tmp][tmp]==-1: dp[tmp][tmp]=value+1
que.append((tmp,tmp)) #클립보드에서 붙여넣기하는 경우
if tmp+clip<len(dp) and dp[tmp+clip][clip]==-1:
dp[tmp+clip][clip]=value+1 que.append((tmp+clip,clip))더 좋은 방법이 있었다.
중복을 허용하지 않기위해 2차원 배열을 만들었는데, 사실 dict로 중복값이 있는지도 판별할 수 있다.
푸는 방법은 위와 거의 동일하다.
import sysinput=sys.stdin.readlinefrom collections import dequen=int(input())
visited={}que=deque()que.append((1,0))visited[(1,0)]=0while que:
tmp,clip=que.popleft() #만일 정답에도달하면 출력 if tmp==n:
print(visited[tmp,clip]) exit()
#tmp, tmp이면, tmp인상태에서 클립보드에 복사한거 #따라서 복사하기전+1
if (tmp,tmp) not in visited.keys():
visited[(tmp,tmp)]=visited[(tmp,clip)]+1 que.append((tmp,tmp))
## 만약 현재상태에서 붙여넣기한 상태를 방문하지 않았으면, ## 다음 상태는 현재 수,클립보드 +1
if (tmp+clip,clip) not in visited.keys():
visited[(tmp+clip,clip)]=visited[(tmp,clip)]+1
que.append((tmp+clip,clip))
if tmp>0 and(tmp-1,clip) not in visited.keys():
visited[(tmp-1,clip)]= visited[(tmp,clip)]+1
que.append((tmp-1,clip))난 아직도 내가 이해했는지도 모르겠다. 일단별표