우주의 IT 소행성

https://www.acmicpc.net/problem/16197

n, m = map(int, input().split())
a = [list(input()) for _ in range(n)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
location = []

for i in range(n):
    for j in range(m):
        if a[i][j] == 'o':
            location.append((i, j))

x1, y1 = location[0]
x2, y2 = location[1]


def go(x1, y1, x2, y2, count):
    is_fall = [False, False] # 동전이 떨어졌는지 여부 파악

    # 버튼을 10번 넘게 누른 경우
    if count == 11:
        return -1

    if (x1 < 0 or x1 >= n or y1 < 0 or y1 >= m):
        is_fall[0] = True
    if (x2 < 0 or x2 >= n or y2 < 0 or y2 >= m):
        is_fall[1] = True

    if is_fall[0] and is_fall[1]:  # 둘 다 떨어진 경우 (불가능)
        return -1

    if is_fall[0] or is_fall[1]:  # 하나만 떨어진 경우 (정답)
        return count

    ans = -1
    for i in range(4):
        nx1, ny1 = x1 + dx[i], y1 + dy[i]
        nx2, ny2 = x2 + dx[i], y2 + dy[i]

        # 이동할 칸이 벽이라면 이동하지 않는걸로
        if 0 <= nx1 < n and 0 <= ny1 < m and a[nx1][ny1] == '#':
            nx1, ny1 = x1, y1
        if 0 <= nx2 < n and 0 <= ny2 < m and a[nx2][ny2] == '#':
            nx2, ny2 = x2, y2

        # 다음 칸으로 진행시켰는데
        temp = go(nx1, ny1, nx2, ny2, count + 1)
        if temp == -1:  # -1 받았다면 무시
            continue
        if ans == -1 or ans > temp:  # -1이 아니라면(정답이라면)
            ans = temp
    return ans

print(go(x1, y1, x2, y2, 0))

네 개의 버튼 (상하좌우)를 통해 두 동전을 동시에 이동시키는데

1. 동전이 벽에 가로 막히면 제자리

2. 동전 하나가 떨어지면 정답

3. 동전 2개가 동시에 떨어지는건 불가능

4. 버튼을 10번이상 사용하면 무효

라는 4가지 조건을 지키며 재귀함수를 통해서 풀어주었다

https://www.acmicpc.net/problem/16953

"""
a - > b
1. 곱하기 2
2. 1을 수의 가장 오른쪽에 추가

"""
a, b = map(int, input().split())
count = 1

def go(a, b, count):
    if a == b:
        print(count)
        exit()
    if a > b:
        return
    go(a * 2, b, count + 1)
    go(int(str(a) + "1"), b, count + 1)


go(a, b, count)
print(-1)

재귀 함수를 이용하여 푼 문제

재귀의 조건을 살펴보자

1. A와 B가 같은 값이면 재귀 종료

2. A가 B보다 커지면 재귀 종료

3. 1-2에 해당하지 않는 경우 매 순간 a에 대해 곱하기 2, 1을 추가 해주면 됨