[백준 1463 파이썬/python] 1로 만들기

1로 만들기

문제

입력

출력

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2

힌트

풀이

1) Bottom Up 풀이 방법(for 반복문 사용)

2) Top Down 풀이 방법(재귀 함수 사용)

3) BFS 풀이

1로 만들기

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
0.15 초 (하단 참고)	128 MB	251622	83928	53625	32.503%

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.

2. X가 2로 나누어 떨어지면, 2로 나눈다.

3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

예제 입력 1

2

예제 출력 1

1

예제 입력 2

10

예제 출력 2

3

힌트

10의 경우에 10 → 9 → 3 → 1 로 3번 만에 만들 수 있다.

풀이

1) Bottom Up 풀이 방법(for 반복문 사용)

def min_operations(n):
    dp = [0] * (n + 1)

    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + 1

        if i % 2 == 0:
            dp[i] = min(dp[i], dp[i // 2] + 1)
        
        if i % 3 == 0:
            dp[i] = min(dp[i], dp[i // 3] + 1)

    return dp[n]

n = int(input())
print(min_operations(n))

• 풀이과정
  1. 먼저, dp라는 이름의 리스트를 만들고 길이를 n + 1로 초기화합니다. 이 리스트는 인덱스 i에 해당하는 정수 i를 1로 만드는 데 필요한 최소 연산 횟수를 저장합니다. 초기에 모든 원소는 0으로 초기화됩니다.
  2. for문을 사용하여 2부터 n까지 반복하면서 각 정수에 대한 최소 연산 횟수를 계산합니다. 먼저, dp[i]를 dp[i - 1] + 1로 설정합니다. 이는 3번 연산(1을 뺀다)을 사용한 경우의 연산 횟수를 나타냅니다.
  3. 다음으로, i가 2로 나누어 떨어지는 경우(즉, i % 2 == 0인 경우)에는 dp[i // 2] + 1과 dp[i] 중 더 작은 값을 dp[i]에 저장합니다. 이렇게 함으로써 2로 나누는 연산을 고려한 최소 연산 횟수를 구할 수 있습니다.
  4. 마찬가지로, i가 3으로 나누어 떨어지는 경우(즉, i % 3 == 0인 경우)에도 dp[i // 3] + 1과 dp[i] 중 더 작은 값을 dp[i]에 저장합니다. 이렇게 함으로써 3으로 나누는 연산을 고려한 최소 연산 횟수를 구할 수 있습니다.
  5. for문이 끝나면 dp[n]에 주어진 정수 N에 대한 최소 연산 횟수가 저장되어 있습니다. 이 값을 반환하여 출력합니다.

2) Top Down 풀이 방법(재귀 함수 사용)

x = int(input())
dp = {1: 0}


def rec(n):
    if n in dp.keys():
        return dp[n]
    if (n % 3 == 0) and (n % 2 == 0):
        dp[n] = min(rec(n // 3) + 1, rec(n // 2) + 1)
    elif n % 3 == 0:
        dp[n] = min(rec(n // 3) + 1, rec(n - 1) + 1)
    elif n % 2 == 0:
        dp[n] = min(rec(n // 2) + 1, rec(n - 1) + 1)
    else:
        dp[n] = rec(n - 1) + 1
    return dp[n]


print(rec(x))

이 코드는 주어진 정수 x를 1로 만드는 데 필요한 최소 연산 횟수를 재귀 함수를 사용하여 찾는 알고리즘입니다.

1. 입력 값을 받아 x에 저장합니다.

2. dp라는 이름의 딕셔너리를 생성하고, 1에 대한 최소 연산 횟수인 0을 저장합니다. 여기서 딕셔너리의 키는 정수 값이고, 값은 해당 정수에 대한 최소 연산 횟수입니다.

3. rec라는 이름의 재귀 함수를 정의합니다. 이 함수는 입력으로 정수 n을 받습니다.
   • 만약 n이 딕셔너리 dp의 키에 있으면, dp[n]을 반환합니다.
   • n이 3으로 나누어 떨어지고 2로도 나누어 떨어지는 경우, 3으로 나눈 결과와 2로 나눈 결과에 대해 재귀 호출을 하고, 그 중 작은 값을 dp[n]에 저장한 후에 1을 더합니다.
   • n이 3으로 나누어 떨어지는 경우, 3으로 나눈 결과와 n에서 1을 뺀 결과에 대해 재귀 호출을 하고, 그 중 작은 값을 dp[n]에 저장한 후에 1을 더합니다.
   • n이 2로 나누어 떨어지는 경우, 2로 나눈 결과와 n에서 1을 뺀 결과에 대해 재귀 호출을 하고, 그 중 작은 값을 dp[n]에 저장한 후에 1을 더합니다.
   • 위의 모든 경우가 아닌 경우, n에서 1을 뺀 결과에 대해 재귀 호출을 한 후에 dp[n]에 저장하고 1을 더합니다.
   • 최종적으로 계산된 dp[n]을 반환합니다.

4. rec(x)를 호출하여 x에 대한 최소 연산 횟수를 계산하고 출력합니다.

이 코드는 재귀 함수를 사용하여 주어진 정수 x를 1로 만드는 데 필요한 최소 연산 횟수를 찾습니다. 하지만 이 방법은 입력 값이 커지면 재귀 호출이 많아져 시간 초과가 발생할 수 있으므로, 앞서 설명한 동적 프로그래밍 방법을 사용하는 것이 효율적입니다.

3) BFS 풀이

from collections import deque

x = int(input())
Q = deque([x])
visited = [0] * (x + 1)
while Q:
    c = Q.popleft()
    if c == 1:
        break
    if c % 3 == 0 and visited[c // 3] == 0:
        Q.append(c // 3)
        visited[c // 3] = visited[c] + 1
    if c % 2 == 0 and visited[c // 2] == 0:
        Q.append(c // 2)
        visited[c // 2] = visited[c] + 1
    if visited[c - 1] == 0:
        Q.append(c - 1)
        visited[c - 1] = visited[c] + 1
print(visited[1])

• BFS란 무엇인가?

  "Breadth-First Search"의 약자. BFS 알고리즘은 너비 우선 탐색 방법으로, 그래프나 트리와 같은 데이터 구조를 탐색하는 데 사용되는 알고리즘입니다. 시작 노드에서부터 인접한 노드들을 먼저 방문한 후, 그 다음 레벨의 노드들을 차례대로 방문하는 방식으로 진행됩니다. 이 과정을 반복하여 그래프나 트리의 모든 노드를 방문할 수 있습니다.

  BFS 알고리즘은 다음과 같은 순서로 수행됩니다:

  1. 시작 노드를 방문 리스트에 넣고, 시작 노드를 큐(Queue)에 추가합니다.

  2. 큐에서 노드를 하나 꺼냅니다.

  3. 꺼낸 노드와 인접한 노드들 중 아직 방문하지 않은 노드들을 큐에 추가하고, 방문 리스트에 표시합니다.

  4. 큐가 비어있을 때까지 2-3단계를 반복합니다.

  BFS 알고리즘의 주요 특징은 다음과 같습니다:

  • BFS는 인접한 노드들을 먼저 방문하므로, 노드들을 거리에 따라 레벨별로 탐색합니다.

  • BFS는 큐(Queue)를 사용하여 노드들을 저장하고 처리합니다. 이로 인해 메모리 사용량이 상대적으로 높을 수 있습니다.

  • BFS는 최단 경로 문제나 최소 신장 트리 문제 등의 최적해를 구하는 데 사용됩니다.

  • 무방향 그래프에서 사이클 여부를 판별하는 데에도 사용될 수 있습니다.

  • 그래프의 연결 성분을 찾거나 두 노드 사이의 최단 경로를 찾는 데 사용할 수 있습니다.

  BFS는 인공지능, 게임 프로그래밍, 네트워크 등 다양한 분야에서 활용되는 중요한 탐색 알고리즘입니다.

• 풀이과정
  1. collections 모듈의 deque를 사용합니다. 이를 통해 큐(Queue)를 구현하고, 탐색하는 노드들을 저장합니다.
  2. 입력 값을 받아 x에 저장합니다.
  3. x를 시작 노드로 하는 큐(Q)를 생성합니다.
  4. 방문한 노드를 기록하기 위한 visited 리스트를 생성하고 초기화합니다. 이 때 리스트의 크기는 x+1로 설정합니다.
  5. 큐가 비어있지 않는 동안 다음 과정을 반복합니다:
     • 큐에서 노드를 하나 꺼냅니다(c = Q.popleft()).
     • 꺼낸 노드 c가 1인 경우, 반복을 종료합니다.
     • c가 3으로 나누어 떨어지고, c//3을 아직 방문하지 않았다면, 큐에 c//3을 추가하고, visited[c//3]에 visited[c]+1을 저장합니다.
     • c가 2로 나누어 떨어지고, c//2를 아직 방문하지 않았다면, 큐에 c//2를 추가하고, visited[c//2]에 visited[c]+1을 저장합니다.
     • c-1을 아직 방문하지 않았다면, 큐에 c-1을 추가하고, visited[c-1]에 visited[c]+1을 저장합니다.
  6. visited[1] 값을 출력합니다. 이 값은 주어진 정수 x를 1로 만드는 데 필요한 최소 연산 횟수입니다.

  이 코드는 BFS 알고리즘을 사용하여 주어진 정수 x를 1로 만드는 최소 연산 횟수를 찾습니다. 이 방법은 노드 간 거리를 기록하는 visited 리스트를 사용하여 반복되는 연산을 줄이고, 결과를 빠르게 도출할 수 있습니다.

Uploaded by N2T