모자란건 고민하는 시간인가 재능인가

#14226번 이모티콘 https://www.acmicpc.net/problem/14226

14226번: 이모티콘

일단 열심히 짰다.

 

T = int(input())
dist = [-1]*(1000+1)
# index = 이모티콘 개수
# value = 연산 횟수


def bfs(T):
    que = [1]
    dist[1] = 0
    copy_data = 0
    while que:
        c = que.pop(0)
        if c == T:
            return dist[c]
        # 이전에 복사한 값 붙여넣어 모든 값 만들기
        if copy_data > 0:
            ni = c + copy_data
            cnt = 1
            while 0 < ni <= T:
                nc = dist[c] + cnt
                dist[ni] = nc if dist[ni] == -1 else min(nc, dist[ni])
                ni += copy_data
                cnt += 1
                que.append(ni)
        # 복사 후 붙여넣기
        ni = c*2
        if 0 < ni <= 1000:
            copy_data = c
            nc = dist[c] + 2
            dist[ni] = nc if dist[ni] == -1 else min(nc, dist[ni])
            que.append(ni)
        # 하나 지우기
        ni = c - 1
        if 0 < ni <= 1000:
            nc = dist[c] + 1
            dist[ni] = nc if dist[ni] == -1 else min(nc, dist[ni])
            que.append(ni)


print(bfs(T))

테스트 케이스만 통과하고 1%도 통과하지 못한 코드이다..

그래서 고민하고 또 고민했지만

뭔가 답이 떠오르지 않았다.

 

결국엔 구글링..

T = int(input())
# 1000가지를 모두 볼 필요 없음. 목표값 + 1까지만 봐도 충분
emoji = [[-1 for _ in range(T+1)] for _ in range(T+1)]
# [이모티콘 개수][클립보드 개수]
# value는 연산횟수


def bfs(T):
    que = []
    que.append((1, 0))
    # 현재 개수, 클립보드의 개수
    emoji[1][0] = 0
    while que:
        x, y = que.pop(0)
        # 최솟값 연산 필요없음, 어차피 처음 연산 값이 최솟값
        # 복사하기
        if emoji[x][x] == -1:
            emoji[x][x] = emoji[x][y] + 1
            que.append((x, x))
        # 붙어넣기
        if x + y <= T and emoji[x+y][y] == -1:
            emoji[x+y][y] = emoji[x][y] + 1
            que.append((x+y, y))
        # 하나 지우기
        if x - 1 >= 0 and emoji[x-1][y] == -1:
            emoji[x-1][y] = emoji[x][y] + 1
            que.append((x-1, y))


bfs(T)
answer = emoji[T][1]
for i in range(1, T):
    if emoji[T][i] != -1:
        answer = min(answer, emoji[T][i])
print(answer)

충격적인 아이디어가 많았다. 일단 데이터를 저장하는 방식 자체가 달랐다. dp와 bfs를 이용하고자 한다면 dp리스트 안에 들어가는 값을 설정해야한다. 내 경험상 bfs를 통해서 연산한다면 dp리스트 안에 들어가는 값은 무조건 비용, 에지의 가중치가 되어야한다.

 

그 외의 데이터는 모두 index로 처리한다.

 

깨달은 점은

 

알고리즘 문제를 풀 때, 뭔가 창의적인 아이디어를 떠올리려 하기보단

기존의 알고리즘에 문제를 끼워맞추는 느낌으로 접근하는게 훨씬 효율이 좋다는 점이다.

 

여전히 부족하다 부족해