BOJ 14226 이모티콘

https://www.acmicpc.net/problem/14226
시간 2초, 메모리 512MB
input :

• S (2 ≤ S ≤ 1000)

output :

• S개 만들기 위해 필요한 시간의 최솟값을 출력

조건 :

• 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만들어
• 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
• 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
• 화면에 있는 이모티콘 중 하나를 삭제한다.
• 모든 연산은 1초가 걸린다.

---

맨 처음 이모티콘 1개로 된 문자열을 주기 때문에 1번 인덱스의 값은 0이다.

그냥 복사, 붙여 넣기 삭제만 구현 하면 되나 싶어서 for문 한번이 가능 한가 싶었지만
이럴 경우에 2의 제곱승의 경우 빼고는 구현이 불가능 하다.

이중 반복문을 사용하던지 bfs를 사용해야 한다.

반복문을 사용한 경우 2배로 곱하는 붙여넣기 연산을 구현 하기 위해선 현재 숫자가 i의 배수인지 판별이 필요하다. 거기에 1초가 더 걸리는 삭제 연산을 구현한다.

for i in range(1, 1000):
    for j in range(i+1, 1001):
        if j == i*2:
            emo[j] = min(emo[i]+2, emo[j])
        elif j%i == 0:
            emo[j] = min(emo[i]+j//i, emo[j])
        
        if emo[j-1] > emo[j]+1:
            emo[j-1] = emo[j]+1

위의 방법 또는 bfs를 이용해서 모든 연산이 처음 수행 되는 경우에 이 값을 업데이트 하고 큐에 넣어 계속 수행할 수 있도록 한다. 2차원 배열을 이용해 수행하기 때문에 이 값이 무엇을 가지고 있는지 확인 해야 하고 범위에 유의 해야 한다.

import sys
from collections import deque

s = int(sys.stdin.readline())
ans = [[-1] * (s + 1) for i in range(s + 1)]
ans[1][0] = 0

q = deque([(1, 0)])

while q:
    x, y = q.popleft()

    if ans[x][x] == -1:
        ans[x][x] = ans[x][y] + 1
        q.append((x, x))

    if x + y <= s and ans[x + y][y] == -1:
        ans[x + y][y] = ans[x][y] + 1
        q.append((x + y, y))

    if x - 1 >= 0 and ans[x - 1][y] == -1:
        ans[x - 1][y] = ans[x][y] + 1
        q.append((x - 1, y))

ret = float('INF')
for item in ans[s]:
    if item != -1 and ret > item:
        ret = item
print(ret)