백준 14226번 이모티콘

 

간단하게 생각해서 클릅보드의 개수를 저장해주자 비용도 저장하고

 

from collections import deque
import sys

n=int(sys.stdin.readline().rstrip())
v=[-1]*2001
def bfs():
    q=deque()
    q.append([1,0,0])
    v[1]=0
    while q:
        cur_v,clip,cost=q.popleft()
        for i in range(3):
            move_v=0
            cur_cost=cost
            cur_clip=clip
            if i==0:
                if clip==0:
                    continue
                move_v=cur_v+clip
                cur_cost+=1
            elif i==1:
                cur_clip=cur_v
                move_v=cur_v
                cur_cost+=1
                if cur_clip!=clip:
                    q.append([move_v,cur_clip,cur_cost])
                    continue
            else:
                move_v=cur_v-1
                cur_cost+=1
            if move_v>2000 or move_v<0:
                continue
            if v[move_v]==-1 or v[move_v]>cur_cost:
                v[move_v]=cur_cost
                q.append([move_v,cur_clip,cur_cost])
bfs()
print(v[n])

이렇게 1차원배열로 별짓을 다해봤지만 풀리지않는다

뭔가 될거같긴한데

from collections import deque
import sys

n=int(sys.stdin.readline().rstrip())
q=deque()

visited=[[-1]*2001 for _ in range(2001)]
q.append([1,0])
visited[1][0]=0
is_end=False
while q:
    cur_v,clip=q.popleft()
    
    for i in range(3):
        move_v=cur_v
        move_clip=clip
        if i==0:
            move_clip=move_v
        elif i==1:
            move_v+=move_clip
        elif i==2:
            move_v-=1
        if move_v<0 or move_v>2000:
            continue
        if move_v==n:
            print(visited[cur_v][clip]+1)
            is_end=True
            break
        if visited[move_v][move_clip]==-1:
            q.append([move_v,move_clip])
            visited[move_v][move_clip]=visited[cur_v][clip]+1
    if is_end:
        break

 

모르겠어서 정답을 한번 봤다

 

1차원으로 풀지 못하는 이유는 동일한 화면개수에 다른 클립보드 개수일때가 문제가 되는것이다.

 

중요한점은 내가 큐에 집어넣었을때 클립보드 복사일때만 큐에 넣고있는데

그렇게 되면 놓치는 경로가 생기는게 문제였다.

클립보드번호도 저장하지 않으면 풀수가 없는 문제였다.

정확히는 큐에 넣는 조건이 코스트가 적을때 넣는건데 이렇게 되면 손실되는 클립이 생긴다.