둔필승총

www.acmicpc.net/problem/11047

문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

예제 입력 1

10 4200

1

5

10

50

100

500

1000

5000

10000

50000

예제 출력 1

6

예제 입력 2

10 4790

1

5

10

50

100

500

1000

5000

10000

50000

예제 출력 2

12

[문제 해설]

n종류의 동전으로 k금액을 만들면 된다. 그리디 알고리즘을 이용해 풀 수 있는 대표적인 문제로 간단한 아이디어만 떠올릴 수 있으면 된다. 그것은 바로 '가장 큰 화폐 단위부터' 나누어 주는 것이다. 물론 k보다 큰 금액이면 나눌 수 없으므로 k보다 작은 것중에 제일 큰 수부터 나누면 된다.

n,k=map(int,input().split())
a=[]
for _ in range(n):
    a.append(int(input()))
a.sort(reverse=True)
ans=0
for i in range(n):
    if a[i]>k:
        continue
    else:
        ans+=k//a[i]
        k=k%a[i]
print(ans)

그리디 알고리즘은 모든 알고리즘 문제에 적용할 수 있는 것은 아니다. 대부분의 문제는 그리디 알고리즘을 이용했을 때 '최적의 해'를 찾을 수 없을 가능성이 많다. 

사실 그냥 머리에 떠올린대로 그리디 해법을 생각했을때 해법이 정당한지 컴토해야 한다. 여기서 그리디 알고리즘을 검증하려면 조건을 유심히 봐야된다.

 괄호 안에 주어진 조건을 자세히 살펴보자. 이 문제에서는 조건이 중요하다.

(1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) Ai는 Ai-1의 배수라는 점. 그리디 알고리즘의 정당성을 부여하려면 예시를 들어보자. 만약 k의 값이 800원이고 Ai 배열에서 500원, 400원, 100원이라면 우리가 짠 그리디 알고리즘으로는 500원 1개, 100원 3개가 최적의 답으로 나온다. 그러나 사실 400원 2개 주는 것이 더 이득이다. 이 문제는 다이나믹 알고리즘으로 따로 풀 수 있다.

 이 문제에서 그리디 알고리즘을 쓸 수 있었던것은 Ai는 Ai-1의 배수라는 사실 때문이다.

아래에서 더 자세히 설명해 두었다.

2020.10.02 - [알고리즘/알고리즘 이론] - 그리디(Greedy) 알고리즘

www.acmicpc.net/problem/1012

[문제 풀이]

문제가 길지만 정리하자면 배추밭에서 1이 있는곳은 배추가 있는곳, 0은 배추가 없는 곳이다. 1이 있는 곳을 DFS해서 주위에 0으로 둘러쌓일때까지 구하고, 그 갯수를 파악해서 출력하면 된다. 혹은 BFS를 통해서 풀 수 있다. (복습을 할 때 BFS를 통해서 풀었다.)

1. 첫번째 풀이법

import sys
sys.setrecursionlimit(10000)
def dfs(x,y):
    if x<=-1 or x>=n or y<=-1 or y>=n:
        return False
    if graph[x][y]==1:
        graph[x][y]=0
        dfs(x-1,y)
        dfs(x+1,y)
        dfs(x,y+1)
        dfs(x,y-1)
        return True
    return False
t = int(input())
for _ in range(t):
    m,n,k=map(int,input().split())
    graph=[[0]*(m) for _ in range(n)]
    result=0
    for _ in range(k):
        x,y=map(int,input().split())
        graph[y][x]=1
    for i in range(n):
        for j in range(m):
            if dfs(i,j):
                result+=1
    print(result)

dfs 함수를 정의해 주면서 먼저 x와 y좌표가 범위를 벗어날때는 False를 반환하게 두었다. 그러나 이렇게 하면 만약 x,y 에 (0,0) 이 들어갔을 경우 index error가 일어나게 된다. 

2. 두번째 풀이법

import sys
sys.setrecursionlimit(10000)
def dfs(x,y):
    dx=[0,0,1,-1]
    dy=[1,-1,0,0]
    for i in range(4):
        nx,ny = x+dx[i],y+dy[i]
        if nx>=n or nx<0 or ny>=m or ny<0:
            continue
        if graph[nx][ny]==1:
            graph[nx][ny]=0
            dfs(nx,ny)
t = int(input())
for _ in range(t):
    m,n,k=map(int,input().split())
    graph=[[0]*(m) for _ in range(n)]
    result=0
    for _ in range(k):
        x,y=map(int,input().split())
        graph[y][x]=1
    for i in range(n):
        for j in range(m):
            if dfs(i,j):
                result+=1
    print(result)

두 번째 풀이법은 dx, dy를 통해서 상하좌우를 탐색하기 때문에 상관없지만 첫번째 풀이법은 의도치 않은 인덱스에 접근할 수 있기때문에 오류가 난다.

3. 세번째 풀이 (BFS를 통해서 해결)

BFS를 통해서 푸는 것으로 익숙해질려고 했다.(DFS를 사용하니까 계속 recursion error 같은 것들을 신경써야해서..) 먼저 BFS는 deque를 사용하므로 상단에 deque를 import 시켜준다.

from collections import deque

bfs는 파라미터로 a,b를 받는다. 여기서 a, b는 배추밭에서 1인 것, 즉 배추가 있는곳을 찾으면 bfs를 실행해서 주위가 0으로 둘러쌓인것에 닿을때까지 실행해준다. 그리고 bfs함수가 끝나면 total_num(우리가 출력해야 되는 값)을 하나 더해준다.

 매번 헷갈리지만 주의해야 할 것은 2차원 배열에 x,y축의 값이다.. 가로가 m이지만 배열의 첫번째는 y축의 값이 들어가는.. 이런것을 계속 생각해주어야 한다. 

from collections import deque
def bfs(a,b):
    q=deque([])
    q.append((a,b))
    graph[a][b]=0
    dx=[-1,1,0,0]
    dy=[0,0,-1,1]
    bechu = 0
    while q:
        x,y=q.popleft()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if nx>=0 and nx<n and ny>=0 and ny<m and graph[nx][ny]==1:
                q.append((nx,ny))
                graph[nx][ny]=0
t = int(input())
for _ in range(t):
    m,n,k = map(int,input().split())
    graph=[[0]*(m) for _ in range(n)]
    total_num = 0
    for i in range(k):
        x,y = map(int,input().split())
        graph[y][x]=1
    for i in range(n):
        for j in range(m):
            if graph[i][j]==1:
                bfs(i,j)
                total_num+=1
    print(total_num)

www.acmicpc.net/problem/11724

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

예제 입력 1

6 5
1 2
2 5
5 1
3 4
4 6

예제 출력 1

2

예제 입력 2

6 8
1 2
2 5
5 1
3 4
4 6
5 4
2 4
2 3

예제 출력 2

1

[문제 해설]

먼저 문제를 해결하려면 연결 요소라는 개념을 알아야 한다. 연결요소란 그래프의 개수와 같다. 정점 사이에 겹쳐진게 없고, 나누어진 각각의 그래프를 연결 요소라고 생각하면 된다. 연결 요소를 구하는 것은 DFS나 BFS 탐색을 이용해서 할 수 있다.

정점의 개수 n과 간선의 개수 m을 먼저 입력 받는다. 그리고 graph라는 2차원 배열을 만들어서 연결된 정보를 얻는다. visited 배열은 각각의 정점에 방문했는지 확인하는것으로 False로 초기화시켜놓는다. 

dfs함수를 만들면 되는데 파라미터로는 v, 즉 노드를 받는다. visited[v]를 True로 대입하고 v와 연결된 곳 중 방문하지 않은 곳을 dfs해준다. 이렇게 dfs를 다 하면 result값을 1 추가한다. 출력값은 result를 출력하면 되는것이다.

import sys
sys.setrecursionlimit(10000)

n,m = map(int,input().split())
graph=[[] for _ in range(n+1)]
visited=[False]*(n+1)
result=0
for _ in range(m):
    u,v = map(int,input().split())
    graph[u].append(v)
    graph[v].append(u)

def dfs(v):
    visited[v]=True
    for i in graph[v]:
        if not visited[i]:
            dfs(i)
for i in range(1,n+1):
    if not visited[i]:
        dfs(i)
        result+=1
print(result)

##의문점##

이 문제를 제출하니까 pypy3으로는 해결되는데 python3으로는 시간초과가 난다. 그래서 질문을 올렸더니...

www.acmicpc.net/board/view/66897#comment-111276

파이썬 루프쪽 구현을 잘못해서 pypy구현체가 훨 빠르다고... 

(나중에 확인해봐야겠다)

www.acmicpc.net/problem/2606

문제

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

출력

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

예제 입력 1

7
6
1 2
2 3
1 5
5 2
5 6
4 7

예제 출력 1

4

[문제 해설]

문제 이해는 아주 잘 되는 편이였다. 1번이 바이러스에 걸리면 1번과 연결된 모든 컴퓨터가 바이러스에 걸린다. 1번에 의해서 몇개의 컴퓨터가 바이러스에 걸리는지 확인하면 되는 문제이다.

먼저 1부터 해서 깊게 파고들어서 연결된 컴퓨터를 모두 확인해야 되기 때문에 DFS를 떠올릴 수 있다. DFS를 통해서 풀었다.

(밑에 코드는 정답은 아니고 시행착오 중 하나)

n = int(input())
m= int(input())
computer=[]
visited=[False]*(n+1)

for i in range(m):
    computer.append(list(map(int,input().split())))

def dfs(computer,v,visited):
    visited[v]=True
    for i in range(m):
        x=computer[i][0]
        y=computer[i][1]
        if not visited[y] and x==v:
            dfs(computer,y,visited)
            print(visited)
dfs(computer,1,visited)
answer=0
for i in range(1,n+1):
    if visited[i]:
        answer+=1
print(answer-1)

위에 코드는 처음에 짠 코드이다. 연결된 간선 모두를 반복문을 통해 확인하고 방문되지 않은곳을 다 방문하여 확인하였다. 예제 입력에 있는 숫자들을 복사하면 출력 값이 잘 나온다.

 그러나 제출하면 계속 '틀렸습니다' 가 되어서 코드를 계속해서 보았다.

 예제 입력을 조금만 틀어서 입력하니까 문제를 찾을 수 있었다.

7
6
1 2
2 3
5 1#여기만 바꿈
5 2
5 6
4 7

사실 연결된 것은 똑같기 때문에 같은 값이 나와야 되는데 출력값은 4가 아니였다. 

양쪽에 연결된 것을 확인하지 않았기 때문이었다.

양쪽에 연결하는 코드를 추가해주면 된다.

n = int(input())
m= int(input())
computer=[]
visited=[False]*(n+1)

for i in range(m):
    computer.append(list(map(int,input().split())))

def dfs(computer,v,visited):
    visited[v]=True
    for i in range(m):
        x=computer[i][0]
        y=computer[i][1]
        if not visited[y] and x==v:
            dfs(computer,y,visited)
        if not visited[x] and y==v:
            dfs(computer,x,visited)
dfs(computer,1,visited)
answer=0
for i in range(1,n+1):
    if visited[i]:
        answer+=1
print(answer-1)

www.acmicpc.net/problem/2667

문제

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

출력

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

예제 입력 1

7
0110100
0110101
1110101
0000111
0100000
0111110
0111000

예제 출력 1

3
7
8
9

[문제 풀이]

일단 <그림1>에서 1이 적힌 곳을 찾아서 0이 나올때까지 끝까지 탐색을 시켜줘야된다. 여기서 깊이 우선 탐색을 생각해 낼 수 있다. 지도에서 공간이 상, 하, 좌, 우로 연결되어 있다고 표현할 수 있으므로 그래프 형태로 모델링 할 수 있다. 

1. 특정한 지점의 주변 상, 하, 좌, 우를 살펴본 뒤에 주변 지점 중에서 값이 '0'이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문한다.

2. 방문한 지점에서 다시 상, 하, 좌, 우를 살펴보면서 방문을 다시 진행하면, 연결된 모든 지점을 방문할 수 있다.

n = int(input())
graph=[]#지도
apt=[]
for _ in range(n):
    graph.append(list(map(int,input())))

def dfs(x,y):
    global cnt
    if x<=-1 or x>=n or y<=-1 or y>=n:
        return False
    if graph[x][y]==1:
        graph[x][y]=0
        cnt+=1
        dfs(x-1,y)
        dfs(x+1,y)
        dfs(x,y+1)
        dfs(x,y-1)
        return True
    return False
cnt=0
for i in range(n):
    for j in range(n):
        if dfs(i,j)==True:
            apt.append(cnt)
            cnt =0
apt.sort()
print(len(apt))
for i in range(len(apt)):
    print(apt[i])

코드를 설명해보겠다.

일단 출력해야 되는 것은 2개이다. 아파트 단지의 개수와 단지 안에 아파트 수이다. apt 리스트에는 아파트 수가 담겨있게 하고 단지 수는 len(apt)로 구할 생각을 했다.

위에서 말했듯이 dfs로 풀었다. 일단 dfs함수에서 x,y 가 갈 수 없는 곳을 갔을 때는 False를 return해 주었다.

그리고 graph에서 값이 1일때 단지 수를 세면 되니까 1일때 graph의 값을 방문했다는 의미로 0을 대입해주고 아파트 수 즉 cnt를 1씩 늘여간다. 

그리고 dfs함수로 상, 하, 좌, 우를 방문한다.

n*n 반복문으로 apt를 구한다.

 강남역에 엄청난 폭우가 쏟아진다고 가정합시다. 정말 재난 영화에서나 나올 법한 양의 비가 내려서, 고층 건물이 비에 잠길 정도입니다.

 그렇게 되었을 때, 건물과 건물 사이에 얼마큼의 빗물이 담길 수 있는지 알고 싶은데요. 그것을 계산해 주는 함수 trapping_rain을 작성해 보려고 합니다.

 함수 trapping_rain은 건물 높이 정보를 보관하는 리스트 buildings를 파라미터로 받고, 담기는 빗물의 총량을 리턴해 줍니다.

 예를 들어서 파라미터 buildings로 [3, 0, 0, 2, 0, 4]가 들어왔다고 합시다. 그러면 0번 인덱스에 높이 3의 건물이, 3번 인덱스에 높이 2의 건물이, 5번 인덱스에 높이 4의 건물이 있다는 뜻입니다. 1번, 2번, 4번 인덱스에는 건물이 없습니다.

그러면 아래의 사진에 따라 총 10 만큼의 빗물이 담길 수 있습니다. 따라서 trapping_rain 함수는 10을 리턴하는 거죠.

이번에는 파라미터 buildings로 [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]가 들어왔다고 합시다. 그러면 아래의 사진에 따라 총 6 만큼의 빗물이 담길 수 있습니다. 따라서 trapping_rain 함수는 6을 리턴하는 거죠

이 정보를 기반으로, trapping_rain 함수를 작성해 보세요!

예시

# 테스트
print(trapping_rain([3, 0, 0, 2, 0, 4]))
print(trapping_rain([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))

10
6

[해설]

빗물이 담기는 양을 계산하려면 각각의 index에 해당하는 빗물의 양을 모두 더하면 된다. 각각의 index에 빗물의 양을 계산하려면 규칙을 파악해야 한다. 

 먼저 예시를 보고 알 수 있는 점은 0번 인덱스와 마지막 인덱스에는 빗물이 담길 수 없다. 그리고 더 큰 건물들 사이에 끼어 있으면 빗물이 담긴다는 것을 알 수 있다. 그리고 구해야 할 것은 얼마의 빗물이 담기는지 알아야 된다.

다음 그림에서 4번 인덱스를 보자. 4번 인덱스는 왼쪽으로 가장 높은 건물은 3번 인덱스에 있고, 4번 인덱스의 오른쪽으로 가장 높은 건물은 7번 인덱스에 있다. 3번 인덱스의 건물은 높이가 2이고, 7번 인덱스의 건물은 높이가 3인다. 그리고 4번 인덱스에 담긴 빗물의 양은 1이다. 

물이 담기는 것은 4번 인덱스 건물의 높이인 1부터 시작해서, 3번 인덱스와 7번 인덱스의 건물 중 더 낮은 높이인 2까지이다. 그래서 1 만큼의 빗물만 담기는 것이다. 

1. 현재 인덱스의 왼쪽에서 가장 높은 건물의 높이를 구한다.

2. 현재 인덱스의 오른쪽에서 가장 높은 건물의 높이를 구한다.

3. 왼쪽과 오른쪽에서 구한 최대값은 2개인데 이 중 더 낮은 건물의 높이를 구한다.

4. 그 높이에서 현재 인덱스에 있는 건물의 높이를 뺀다.

def trapping_rain(buildings):
    total=0
    for i in range(1,len(buildings)-1):
        max_left=max(buildings[:i])
        max_right=max(buildings[i:])

        upper_bound = min(max_left,max_right)

        total += max(0,upper_bound-buildings[i])
    return total
# 테스트
print(trapping_rain([3, 0, 0, 2, 0, 4]))
print(trapping_rain([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))

www.acmicpc.net/problem/2798

문제

카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다.

한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다.

김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다.

이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다.

N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력하시오.

입력

첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다.

합이 M을 넘지 않는 카드 3장을 찾을 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 출력한다.

예제 입력 1

5 21

5 6 7 8 9

예제 출력 1

21

예제 입력 2

10 500

93 181 245 214 315 36 185 138 216 295

예제 출력 2

497

[문제 해설]

먼저 해볼 수 있는 생각은 카드를 3개 뽑아서 m을 넘지않는 수를 뽑는 것이다. 간단하게 3중 포문을 돌려서 3개의 카드가 같지 않고 m을 넘지 않을때 값을 저장해 둔다. 이 값들 중 최대의 것을 뽑으면 된다. m보다 작은 값이 나올 수도 있으므로 나온 값들 중 최대를 뽑으면 되는것이다.

1. m을 넘는 경우 출력을 안하는 것을 생각해 주어야 한다.

2. 3중 for문을 돌릴 때 3개가 동일한 값이 들어가면 안되니까 조건을 추가해준다.

n,m = map(int,input().split())
cards=list(map(int,input().split()))
answer=0
for i in cards:
    for j in cards:
        for k in cards:
            if i!=j and i!=k and j!=k:
                sum=i+j+k
                if sum>m:
                    continue
                else:
                    answer=max(answer,sum)
print(answer)

하노이 탑 

www.acmicpc.net/problem/1914

문제

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

아래 그림은 원판이 5개인 경우의 예시이다.

입력

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 100)이 주어진다.

출력

첫째 줄에 옮긴 횟수 K를 출력한다.

N이 20 이하인 입력에 대해서는 두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다. N이 20보다 큰 경우에는 과정은 출력할 필요가 없다.

예제 입력 1

3

예제 출력 1

7 1 3 1 2 3 2 1 3 2 1 2 3 1 3

[문제 해설]

막대가 3개가 있을때 생각해보자. 맨 밑에 젤 큰 원판 말고 나머지를 두번째 막대에 옮기고, 젤 큰 원판을 3번째 막대로 옮긴 뒤에, 두번째 막대에 있는 원판들을 3번째 막대로 옮기면 된다. 이걸 재귀 함수를 사용해서 풀면 된다.

mid_peg=(6-start_peg-end_peg) 인 이유 1,2,3 세 개니까 다 더하면 6임. 거기서 start_peg랑 end_peg를 빼면 나머지가 나옴. 거기로 옮겨야됨.

재귀함수에는 recursive case와 base case가 있다.

1. 원판이 없을때에는 아무것도 안해도 게임이 끝남( base case )

def hanoi(num_disks,start_peg,end_peg):
	if num_disks==0:
    	return

2. 원판이 하나 있을 경우에는 1번 기둥에서 3번 기둥으로 옮기면 끝난다. ( base case )

3. 원판이 2개인 경우에는 1번 원판을 1번 기둥에서 2번 기둥으로 옮기고, 2번 원판을 1번기둥에서 3번기둥으로 옮기고 1번 원판을 2번 기둥에서 3번 기둥으로 옮기면 된다.

4. 3번을 생각하면 recursive case에 관해서도 구할 수 있다.

def move_check(start,end):
    print(start,end)

def hanoi(move,start,end):
    if move==1:
        return move_check(start,end)
    other=6-start-end
    hanoi(move-1,start,other)
    move_check(start,end)
    hanoi(move-1,other,end)

일단 move_check(start,end) 함수는 start에서 end로 가는 것을 출력해 주는 함수라고 생각하면 된다.

그 다음 hanoi(move,start,end) 함수를 보자. 이 함수를 만든 것은 move를 start에서 end로 옮긴다고 생각하면 된다.

other은 start와 end가 아닌 나머지 기둥의 숫자이다. 1,2,3 세 개의 기둥이 있으므로 1 +2 + 3 = 6이다.

6에서 start와 end를 빼주면 other이 나올 것이다.

일단 맨 밑의 기둥 빼고 나머지를 other기둥에 두고 맨 밑에 탑을 end에 두고 other기둥에 있는 것을 end에 두면 된다.

이게 순서대로

hanoi(move-1,start,other)
move_check(start,end)
hanoi(move-1,other,end)

이렇게 되는 것이다. move_check로 하나하나 출력할 수 있다.

!!이 문제를 풀 때 주의할 점

1. 총 옮겨야 되는 것을 먼저 출력해 주어야 된다. 총 수를 구할려면 규칙을 찾으면 된다.

  탑이 하나일 때는 1번, 두 개일 때는 3번, 세 개일때는 7번... 규칙을 찾으면 sum*2+1을 하면 된다는 것이 보인다.

  이것을 먼저 출력해주자.

sum=0
for i in range(n):
    sum=sum*2+1

2. 이 문제에서 출력 초과가 계속 난다면 n이 20이 넘을때 과정을 생략해도 된다는 문제 설명을 읽었는지 확인하자!!

(나도 이것때매 문제를 계속 다시 보았다)

if n>20:
    print(sum)
else:
    print(sum)
    hanoi(n,1,3)

[정답]

n = int(input())
k=0
def move_check(start,end):
    print(start,end)
def hanoi(move,start,end):
    if move==1:
        return move_check(start,end)
    other=6-start-end
    hanoi(move-1,start,other)
    move_check(start,end)
    hanoi(move-1,other,end)
sum=0
for i in range(n):
    sum=sum*2+1

if n>20:
    print(sum)
else:
    print(sum)
    hanoi(n,1,3)