728x90
반응형

문제:

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력:

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.

출력:

첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.

풀이방법:

www.acmicpc.net/problem/2293 의 동전 1 문제를 응용해서 풀면 된다. 이 문제에서는 k원을 만드는 경우의 수를 구하는 문제였지만, 이 문제에서는 최솟값을 구해야 한다. 따라서 동전의 가치가 최대 100,000원이므로 초기값으로 100,001원(0원은 0으로 초기화 한다.) 으로 설정하고, 작은 동전부터 사용해서 각 p원을 만들 수 있는 최소 갯수를 구하도록 한다.

 

 이 문제의 예시로 생각하면 다음과 같다. (1,5,12)원이 있을 때, 1원으로 15원을 만드는 방법은 다음과 같이 비교할 것이다.

 

 위 표는 다음 두 조건을 비교하면서 채워나갔다. 1원을 만드는 경우로 예시를 든다.

1. 현재 값을 그대로 사용한다. dp[1]

2. 0원에서 1원을 더해서 사용한다. dp[1-1]+1

3. 1과 2중 더 작은 값을 사용한다. min(dp[1],dp[1-1]+1)

 

즉 이를 일반화 하면 다음과 같다. min(dp[n],dp[n-c]+1), n은 현재 만들고자 하는 금액, c는 현재 사용하고 있는 동전의 가치다.

 

 5원을 사용하는 경우는 1~4원은 만드는 것이 불가능하므로 5원부터 반복한다.

 12원을 사용하는 경우는 1~11원은 만드는 것이 불가능하므로 12부터 반복한다.

 최종적으로는 dp[k]원이 초기화한 값에서 변경이 되었다면 dp[k]를 출력하고, 바뀌지 않았다면 -1을 출력하도록 한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
n,k = map(int,input().split())
coin = []
for _ in range(n):
    coin.append(int(input()))
 
dp=[100001]*(k+1)
dp[0]=0
 
for c in coin:
    for i in range(c,k+1):
        dp[i]=min(dp[i],dp[i-c]+1)
 
if dp[k]==100001:
    print(-1)
else:
    print(dp[k])
cs

 

문제링크:

www.acmicpc.net/problem/2294

 

2294번: 동전 2

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주

www.acmicpc.net

 

728x90
반응형

'Algorithm > Python' 카테고리의 다른 글

[BOJ]1527. 금민수의 개수  (0) 2020.12.22
[BOJ]7453. 합이 0인 네 정수  (0) 2020.12.10
[BOJ]11060. 점프 점프  (0) 2020.12.03
[BOJ]10835. 카드게임  (0) 2020.12.01
[BOJ]1747. 소수&팰린드롬  (0) 2020.11.26
728x90
반응형

문제:

재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 떨어진 칸으로 한 번에 점프할 수 있다. 예를 들어, 3번째 칸에 쓰여 있는 수가 3이면, 재환이는 4, 5, 6번 칸 중 하나로 점프할 수 있다.

재환이는 지금 미로의 가장 왼쪽 끝에 있고, 가장 오른쪽 끝으로 가려고 한다. 이때, 최소 몇 번 점프를 해야 갈 수 있는지 구하는 프로그램을 작성하시오. 만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다.

입력:

첫째 줄에 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 Ai (0 ≤ Ai ≤ 100)가 주어진다.

출력:

재환이가 최소 몇 번 점프를 해야 가장 오른쪽 끝 칸으로 갈 수 있는지 출력한다. 만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다.

풀이방법:

0으로 초기화 된 DP 배열을 미로의 값에 따라 초기화 하면서 진행하면 된다.

이 문제의 예제를 통해서 설명한다. 처음에는 다음과 같이 초기화 된다.

 

1 2 0 1 3 2 1 5 4 2
0 0 0 0 0 0 0 0 0 0

 

numbers[0]의 값은 1이므로 dp[1]의 값을 업데이트한다.

 

1 2 0 1 3 2 1 5 4 2
0 1 0 0 0 0 0 0 0 0

 

numbers[1]의 값은 2이므로 dp[2]~dp[3]의 값을 업데이트한다.

 

1 2 0 1 3 2 1 5 4 2
0 1 2 2 0 0 0 0 0 0

 

numbers[2]의 값은 0이므로 넘어가고, numbers[5]까지 반복하면 아래와 같이 된다.

 

1 2 0 1 3 2 1 5 4 2
0 1 2 2 3 4 4 4 0 0

 

 만약 이미 dp[i+j]에 0이 아닌 다른 값이 초기화되어 있다면, dp[i+j]값과 dp[i]+1값 중 작은 값을 사용하도록 한다. 끝까지 진행하면 다음과 같이 된다.

 

1 2 0 1 3 2 1 5 4 2
0 1 2 2 3 4 4 4 5 5

 위 작업을 모두 반복했을 때, 맨 마지막 값이 0이 아닌 다른 값으로 바뀌었다면, 끝에 도달할 수 있는 것이므로 해당 값을 출력하면 되고, 아니라면 -1을 출력하도록 한다. 그리고 생각해야 하는 예외가 두가지가 있다.

 첫번째는 5 (0,0,0,1,0)과 같은 경우가 있다. 이런 경우는 if dp[i]==0 and i!=0 와 같은 조건문을 넣어서 해결해준다. 정상적으로 진행될 때, dp에 0 값은 dp[0]을 제외하고 생기면 안되기 때문이다.

 두번째는 1 (0) 이다. 이 경우에는 시작과 동시에 오른쪽 끝으로 도달한 경우이기 때문에, 마지막 출력하는 단계에서 예외처리로 0을 출력하도록 한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
N=int(input())
numbers = list(map(int,input().split()))
 
dp = [0]*N
for i in range(N):
    if dp[i]==0 and i!=0:
        continue
    for j in range(1,numbers[i]+1):
        if i+j<N:
            if dp[i+j]:
                dp[i+j]= min(dp[i]+1,dp[i+j])
            else:
                dp[i+j]=dp[i]+1
 
if dp[-1]==0:
    if N==1:
        print(0)
    else:
        print(-1)
else:
    print(dp[-1])
cs

문제링크:

www.acmicpc.net/problem/11060

 

11060번: 점프 점프

재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로

www.acmicpc.net

 

728x90
반응형

'Algorithm > Python' 카테고리의 다른 글

[BOJ]7453. 합이 0인 네 정수  (0) 2020.12.10
[BOJ]2294. 동전 2  (0) 2020.12.08
[BOJ]10835. 카드게임  (0) 2020.12.01
[BOJ]1747. 소수&팰린드롬  (0) 2020.11.26
[BOJ]1707. 이분 그래프  (0) 2020.11.24
728x90
반응형

문제:

지훈이는 최근에 혼자 하는 카드게임을 즐겨하고 있다. 게임에 사용하는 각 카드에는 양의 정수 하나가 적혀있고 같은 숫자가 적힌 카드는 여러 장 있을 수 있다. 게임방법은 우선 짝수개의 카드를 무작위로 섞은 뒤 같은 개수의 두 더미로 나누어 하나는 왼쪽에 다른 하나는 오른쪽에 둔다. 그리고 빈 통을 하나 준비한다.

이제 각 더미의 제일 위에 있는 카드끼리 서로 비교하며 게임을 한다. 게임 규칙은 다음과 같다. 지금부터 왼쪽 더미의 제일 위 카드를 왼쪽 카드로, 오른쪽 더미의 제일 위 카드를 오른쪽 카드로 부르겠다.

  1. 언제든지 왼쪽 카드만 통에 버릴 수도 있고 왼쪽 카드와 오른쪽 카드를 둘 다 통에 버릴 수도 있다. 이때 얻는 점수는 없다.
  2. 오른쪽 카드에 적힌 수가 왼쪽 카드에 적힌 수보다 작은 경우에는 오른쪽 카드만 통에 버릴 수도 있다. 오른쪽 카드만 버리는 경우에는 오른쪽 카드에 적힌 수만큼 점수를 얻는다.
  3. (1)과 (2)의 규칙에 따라 게임을 진행하다가 어느 쪽 더미든 남은 카드가 없다면 게임이 끝나며 그때까지 얻은 점수의 합이 최종 점수가 된다. 

다음 예는 세 장 씩 두 더미의 카드를 가지고 게임을 시작하는 경우이다.

이 경우, 우선 오른쪽 카드 2가 왼쪽 카드 3보다 작으므로 규칙 (1)에 따라 왼쪽 카드만 버리거나 왼쪽 카드와 오른쪽 카드를 모두 버리거나, 규칙 (2)에 따라 오른쪽 카드만 버릴 수 있다. 만약 오른쪽 카드만 버리는 것으로 선택하면, 2만큼 점수를 얻고 오른쪽 카드 2는 버린다. 이제 오른쪽 더미의 제일 위 카드는 4이고 이는 왼쪽 카드 3보다 크므로 규칙 (1)에 따라 왼쪽 카드만 버리거나 왼쪽 카드와 오른쪽 카드를 둘 다 버릴 수 있다. 만약 둘 다 버리는 것으로 선택하면, 이제 왼쪽 카드는 2가 되고 오른쪽 카드는 1이 된다. 이 경우 다시 규칙 (1)과 (2)에 따라 세 가지 중 한가지를 선택할 수 있고, 그 중 왼쪽 카드만 버리는 것으로 선택하면 이제 왼쪽 카드는 5가 되고 오른쪽 카드는 1이 된다. 이 경우에도 역시 규칙 (1)과 (2)에 따라 세 가지 중 한가지를 선택할 수 있고, 그 중 오른쪽 카드만 버리는 것으로 선택하면 1만큼 점수를 얻고 오른쪽 카드 1은 버린다. 이제 오른쪽 더미에는 남은 카드가 없으므로 규칙 (3)에 따라 게임이 끝나며 최종 점수는 2+1=3이 된다.

두 더미의 카드가 주어졌을 때, 게임을 통해 얻을 수 있는 최종 점수의 최댓값을 출력하는 프로그램을 작성하시오. 위 예에서 최종 점수의 최댓값은 7이다.

입력:

첫 줄에는 한 더미의 카드의 개수를 나타내는 자연수 N(1 ≤ N ≤ 2,000)이 주어진다. 다음 줄에는 왼쪽 더미의 카드에 적힌 정수 A(1 ≤ A ≤ 2,000)가 카드 순서대로 N개 주어진다. 그 다음 줄에는 오른쪽 더미의 카드에 적힌 정수 B(1 ≤ B ≤ 2,000)가 카드 순서대로 N개 주어진다. 각 더미에는 같은 숫자를 가진 카드가 두 개 이상 있을 수 있다.

출력:

얻을 수 있는 최종 점수의 최댓값을 출력한다.

풀이방법:

 DP를 사용해서 풀어야 하는 문제다. 처음에는 재귀로 이 문제를 접근했었는데, 시간초과랑 메모리 초과가 반복적으로 발생해서 반복문을 사용해서 풀게 되었다. 반복문을 사용해서 풀게 될 경우에는 정방향으로 DP를 배치하는 것이 아닌, 역방향으로 DP를 구성해야 한다고 한다. 마치 재귀로 풀이 되던 것들이 반복문으로 풀어져서 풀이 된다고 생각하면 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import sys
 
= int(sys.stdin.readline())
left = list(map(int,sys.stdin.readline().split()))
right = list(map(int,sys.stdin.readline().split()))
 
dp = [[0 for _ in range(N+1)] for _ in range(N+1)]
 
for i in range(N-1,-1,-1):
    for j in range(N-1,-1,-1):
        if right[i] < left[j]:
            dp[i][j] = dp[i+1][j]+right[i]
        else:
            dp[i][j] = max(dp[i][j+1],dp[i+1][j+1])
            
print(dp[0][0])
cs

문제링크:

www.acmicpc.net/problem/10835

 

10835번: 카드게임

첫 줄에는 한 더미의 카드의 개수를 나타내는 자연수 N(1 ≤ N ≤ 2,000)이 주어진다. 다음 줄에는 왼쪽 더미의 카드에 적힌 정수 A(1 ≤ A ≤ 2,000)가 카드 순서대로 N개 주어진다. 그 다음 줄에는 오

www.acmicpc.net

 

728x90
반응형

'Algorithm > Python' 카테고리의 다른 글

[BOJ]2294. 동전 2  (0) 2020.12.08
[BOJ]11060. 점프 점프  (0) 2020.12.03
[BOJ]1747. 소수&팰린드롬  (0) 2020.11.26
[BOJ]1707. 이분 그래프  (0) 2020.11.24
[BOJ]7562. 나이트의 이동  (0) 2020.11.19
728x90
반응형

문제:

어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다.

어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N이 주어진다.

출력:

첫째 줄에 조건을 만족하는 수를 출력한다.

풀이방법:

 소수를 판정하는 알고리즘 중 에라토느테네스의 체와 팰린드롬 알고리즘을 함께 사용하는 알고리즘이다. N으로 들어올 수 있는 가장 큰 숫자인 1,000,000에 해당하는 답은 1003001이라는 사실을 사용해서 그 만큼을 sosu 리스트를 초기화했다. (혹은 넉넉하게 큰 길이로 초기화해도 된다.) 이 sosu 리스트를 에라토스테네스의 체를 사용해서 소수만 남겨둔다.

 이후 while 반복문을 통해서 sosu이면서 팰린드롬인 경우에 그 숫자를 출력하고 break를 통해 정지시키면 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def checkpen(m):
    temp = str(m)
    for i in range(len(temp)//2):
        if temp[i]!=temp[len(temp)-i-1]:
            return False
    return True
    
= int(input())
 
sosu = [True]*1003002
sosu[0],sosu[1]=False,False
for i in range(2,len(sosu)):
    if sosu[i]:
        for j in range(2*i,len(sosu),i):
            sosu[j]=False
 
while True:
    if sosu[N] and checkpen(N):
        print(N)
        break
    N+=1
cs

문제링크:

www.acmicpc.net/problem/1747

728x90
반응형

'Algorithm > Python' 카테고리의 다른 글

[BOJ]11060. 점프 점프  (0) 2020.12.03
[BOJ]10835. 카드게임  (0) 2020.12.01
[BOJ]1707. 이분 그래프  (0) 2020.11.24
[BOJ]7562. 나이트의 이동  (0) 2020.11.19
[BOJ]1992. 쿼드트리  (0) 2020.11.17
728x90
반응형

문제:

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

입력:

입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 E(1≤E≤200,000)가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호가 빈 칸을 사이에 두고 주어진다.

출력:

K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.

풀이방법:

 위키피디아에 따르면 이분 그래프란 모든 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 그래프이다. 즉 한 변의 양 끝은 빨강과 파랑으로 서로 달라야 한다는 것이다.

 dfs로 정점을 탐색하며, visited에다 색을 기록한다. dfs로 탐색하는 도중에 visited에 서로 다른 색이 들어오게 되면 이분그래프가 아니므로 False를 반환하도록 한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import sys
 
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
 
def dfs(cur,color):
    visited[cur] = color
    for i in vertex[cur]:
        if visited[i]==0:
            if not dfs(i,-color):
                return False
        elif visited[i] == visited[cur]:
            return False
    return True
 
= int(input())
for _ in range(K):
    V, E = map(int,input().split())
    vertex = [[] for _ in range(V+1)]
    visited = [0 for _ in range(V+1)]
    for _ in range(E):
        x, y = map(int,input().split())
        vertex[x].append(y)
        vertex[y].append(x)
        
    answer = True
    for i in range(1,V+1):
        if visited[i] == 0:
            if not dfs(i,1):
                answer=False
                break
    if answer:
        print("YES")
    else:
        print("NO")
cs

문제링크:

www.acmicpc.net/problem/1707

 

1707번: 이분 그래프

입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수

www.acmicpc.net

 

728x90
반응형

'Algorithm > Python' 카테고리의 다른 글

[BOJ]10835. 카드게임  (0) 2020.12.01
[BOJ]1747. 소수&팰린드롬  (0) 2020.11.26
[BOJ]7562. 나이트의 이동  (0) 2020.11.19
[BOJ]1992. 쿼드트리  (0) 2020.11.17
[BOJ]1041. 주사위  (0) 2020.11.12
728x90
반응형

문제:

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력:

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력:

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

풀이방법:

너비 우선 탐색의 가장 기초적인 문제다. 이미 지나온 곳을 다시 방문하지 않도록 0으로 초기화된 visited 배열을 만들었고, 현재 stage에서 나이트가 있을 수 있는 위치를 able이라는 배열에 저장하도록 했다. 

bfs 함수 내에선 우선 able 내에 목적지가 있는지 확인하는 과정을 먼저 거친다. 있다면 현재 stage(count)를 출력하도록 하고, 없으면 나이트가 움직일 수 있는 경우의 수인 candidate를 able을 각 케이스에 대해 더해줘서 새로운 able을 만들도록 한다. 이 과정을 재귀적으로 반복하면서 값을 찾는다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
candidate = [(2,1),(1,2),(2,-1),(1,-2),(-1,2),(-1,-2),(-2,1),(-2,-1)]
def bfs(able,visited):
    global count
    if (eX,eY) in able:
        print(count)
    else:
        count+=1
        temp = []
        for a in able:
            for c in candidate:
                nx,ny = a[0]+c[0],a[1]+c[1]
                if 0<=nx<and 0<=ny<and visited[nx][ny]==0:
                    visited[nx][ny]=1
                    temp.append((nx,ny))
        bfs(temp,visited)
            
N=int(input())
for _ in range(N):
    l = int(input())
    sX,sY = map(int,input().split())
    eX,eY = map(int,input().split())
    visited = [[0 for _ in range(l)]for _ in range(l)]
    count=0
    able = [(sX,sY)]
    visited[sX][sY] = 1
    bfs(able,visited)
cs

문제링크:

www.acmicpc.net/problem/7562

 

7562번: 나이트의 이동

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수

www.acmicpc.net

 

728x90
반응형

'Algorithm > Python' 카테고리의 다른 글

[BOJ]1747. 소수&팰린드롬  (0) 2020.11.26
[BOJ]1707. 이분 그래프  (0) 2020.11.24
[BOJ]1992. 쿼드트리  (0) 2020.11.17
[BOJ]1041. 주사위  (0) 2020.11.12
[BOJ]1059. 수2  (0) 2020.11.10
728x90
반응형

문제:

흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다.

주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다.

위 그림에서 왼쪽의 영상은 오른쪽의 배열과 같이 숫자로 주어지며, 이 영상을 쿼드 트리 구조를 이용하여 압축하면 "(0(0011)(0(0111)01)1)"로 표현된다.  N ×N 크기의 영상이 주어질 때, 이 영상을 압축한 결과를 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1≤N ≤64의 범위를 가진다. 두 번째 줄부터는 길이 N 의 문자열이 N 개 들어온다. 각 문자열은 0 또는 1의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.

출력:

영상을 압축한 결과를 출력한다.

풀이방법:

 분할정복을 사용해서 풀어야 하는 문제다. 반복해서 영상을 4분할로 나누면서, 같은 숫자로 구성되어 있는지 파악하면 된다.

 각 분할된 분면에서 왼쪽 상단에 있는 점을 기준점으로 삼아서, 반복문을 순회하면서 같은 숫자로 구성되어 있는지 확인한다.

 만약 같은 숫자로 구성되어 있으면 더 이상 분할할 필요가 없으니 현재 기준점을 출력하도록 한다. 하지만 같은 숫자로 구성되어 있지 않다면 재귀적으로 지금 영상을 4분할로 나눠서 위의 작업을 반복해주면 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
= int(input())
numbers=[]
for _ in range(N):
    numbers.append(list(map(int,list(input()))))
 
def quadTree(N,x,y):
    curr = numbers[x][y]
    divide = False
    for i in range(x,x+N):
        for j in range(y,y+N):
            if numbers[i][j]!=curr:
                divide=True
    if divide:
        print("(",end="")
        quadTree(N//2,x,y) # leftupper
        quadTree(N//2,x,y+N//2# rightupper
        quadTree(N//2,x+N//2,y) # leftunder
        quadTree(N//2,x+N//2,y+N//2# rightunder
        print(")",end="")
    else:
        print(curr,end="")
quadTree(N,0,0)
cs

문제링크:

www.acmicpc.net/problem/1992

 

1992번: 쿼드트리

첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1≤N ≤64의 범위를 가진다. 두 번째 줄부터는 길이 N 의 문자열이 N 개 들어온다. 각 문자열은 0 또는

www.acmicpc.net

 

728x90
반응형

'Algorithm > Python' 카테고리의 다른 글

[BOJ]1707. 이분 그래프  (0) 2020.11.24
[BOJ]7562. 나이트의 이동  (0) 2020.11.19
[BOJ]1041. 주사위  (0) 2020.11.12
[BOJ]1059. 수2  (0) 2020.11.10
[BOJ]10775. 공항  (0) 2020.10.29
728x90
반응형

문제:

주사위는 위와 같이 생겼다. 주사위의 여섯 면에는 수가 쓰여 있다. 위의 전개도를 수가 밖으로 나오게 접는다.

A, B, C, D, E, F에 쓰여 있는 수가 주어진다.

지민이는 현재 동일한 주사위를 N^3개 가지고 있다. 이 주사위를 적절히 회전시키고 쌓아서, N*N*N크기의 정육면체를 만들려고 한다. 이 정육면체는 탁자위에 있으므로, 5개의 면만 보인다.

N과 주사위에 쓰여 있는 수가 주어질 때, 보이는 5개의 면에 쓰여 있는 수의 합의 최솟값을 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에 N이 주어진다. 둘째 줄에 주사위에 쓰여 있는 수가 주어진다. 위의 그림에서 A, B, C, D, E, F에 쓰여 있는 수가 차례대로 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, 쓰여 있는 수는 50보다 작거나 같은 자연수이다.

출력:

첫째 줄에 문제의 정답을 출력한다.

풀이방법:

 주사위를 쌓아서 N*N*N 크기의 정육면체를 만들게 되면, 밖으로 노출되는 면이 가장 많은 경우는 3개인 면인 경우이다. 정육면체에서 3개의 면 주사위의 개수, 2개의 면 주사위의 개수, 1개의 면 주사위의 개수는 N에 따라서 달라지게 된다.

 

1. 3개의 면 주사위의 개수는 항상 위쪽 면의 꼭짓점에서만 나타나므로 N과 상관없이 4번만 등장하게 된다.

2. 2개의 면이 나타나는 주사위의 개수는 모서리에서만 나타나게 된다. 이 때 위쪽 면에서는 꼭짓점에서 이미 사용한 주사위가 있으므로 이를 제외해주고 계산해줘야 한다. 따라서 (N-1)*4+(N-2)*4개가 존재한다.

3. 1개의 면이 나타나는 주사위는 ((N-2)^2)*5+(N-2)*4 개 있다.

 

 주사위는 위 그림에서 나타나는 것처럼 전개도를 따라서 접게 되므로, 모든 숫자 중에서 가장 작은 3개(혹은 2개)를 골라서 최솟값을 구하면 안된다. A에 있는 숫자는 F와 만날 수 없기 때문이다. 따라서 나타날 수 있는 3개인 경우는 [(0,1,2),(0,1,3),(0,2,4),(0,3,4),(1,2,5),(1,3,5),(2,4,5),(3,4,5)]와 같기 때문에 이 중에서 가장 작은 값을 가지는 경우를 찾도록 하고, 2개인 경우는 서로 반대 면에 있는 숫자만 피하면 되므로, 이를 제외하고 계산하도록 한다.

 N이 1인 경우는 위에서 구한 케이스 구분이 필요없기 때문에 따로 처리하도록 한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import copy
 
def threemin(numbers):
    candidate = [(0,1,2),(0,1,3),(0,2,4),(0,3,4),(1,2,5),(1,3,5),(2,4,5),(3,4,5)]
    answer = sum(numbers)
    for c in candidate:
        temp = 0
        for idx in c:
            temp +=numbers[idx]
        answer = min(answer,temp)
    return answer
 
def twomin(numbers):
    answer = sum(numbers)
    for i in range(len(numbers)):
        for j in range(i+1,len(numbers)):
            temp = 0
            if i+j==5:
                continue
            else:
                temp += (numbers[i]+numbers[j])
                answer = min(temp,answer)
    return answer
        
 
= int(input())
numbers = list(map(int,input().split()))
 
answer = 0
if N==1:
    answer = sum(numbers)-max(numbers)
else:
    three = threemin(numbers)
    two = twomin(numbers)
    answer += three*4
    answer += two*(N-1)*4+two*(N-2)*4
    answer += min(numbers)*(N-2)*(N-2)*5+min(numbers)*(N-2)*4
print(answer)
cs

문제링크:

www.acmicpc.net/problem/1041

 

1041번: 주사위

첫째 줄에 N이 주어진다. 둘째 줄에 주사위에 쓰여 있는 수가 주어진다. 위의 그림에서 A, B, C, D, E, F에 쓰여 있는 수가 차례대로 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, 쓰여 있는 수

www.acmicpc.net

 

728x90
반응형

'Algorithm > Python' 카테고리의 다른 글

[BOJ]7562. 나이트의 이동  (0) 2020.11.19
[BOJ]1992. 쿼드트리  (0) 2020.11.17
[BOJ]1059. 수2  (0) 2020.11.10
[BOJ]10775. 공항  (0) 2020.10.29
[BOJ]1786. 찾기  (0) 2020.10.27
728x90
반응형

문제:

Lucky Set이란 정수의 집합이다.

구간 [A,B]란 A보다 크거나 같고, B보다 작거나 같은 모든 정수가 있는 구간이다. 이때, A와 B는 모두 양수이고, B는 A보다 크다.

구간 [A,B]가 Unlucky가 되기 위해선 구간에 속한 모든 정수가 Lucky Set에 없어야 한다.

Lucky Set과 N이 주어질 때, N을 포함하는 Unlucky 구간의 개수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 Lucky Set에 포함된 숫자의 개수 L이 주어진다. 둘째 줄에는 L개의 수가 주어진다. 이 수는 1,000보다 작거나 같은 자연수이고, L은 50보다 작거나 같은 자연수이다. 그리고 중복되지 않는다. 마지막 줄에는 N이 주어진다. N은 lucky Set에서 가장 큰 수보다 작거나 같은 자연수이다.

출력:

첫재 줄에 문제의 정답을 출력한다.

풀이방법:

N이 Lucky set의 어느 구간에 속해 있는지 파악해야 한다. 이 때, N이 lucky set의 원소일 수 있으므로 주의해서 탐색해야 한다. 반복문을 사용해서 N이 속해 있는 구간을 파악하고 왼쪽 값을 left, 오른쪽 값을 right라고 설정한다. N이 lucky set의 원소보다 다 작은 경우는 예외케이스로 판단하도록 한다.

left 와 right를 구한 뒤에는 이중반복문을 사용해서 구간을 생성하여, 이 구간 내에 N이 있는 경우에만 answer에 값을 더하도록 한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
= int(input())
lucky = list(map(int,input().split()))
lucky.sort()
answer = 0
= int(input())
left,right = 00
if N<lucky[0]:
    left=0
    right=lucky[0]
elif N == lucky[0]:
    pass
else:
    for i in range(1,len(lucky)):
        if N == lucky[i]:
            break
        elif lucky[i-1< N and lucky[i] > N:
            left = lucky[i-1]
            right = lucky[i]
            break
            
if left+right==0:
    print(answer)
else:
    for l in range(left+1,right):
        for r in range(l+1,right):
            if l<=N<=r:
                answer+=1
    print(answer)
cs

문제링크:

www.acmicpc.net/problem/1059

 

1059번: 수2

첫째 줄에 Lucky Set에 포함된 숫자의 개수 L이 주어진다. 둘째 줄에는 L개의 수가 주어진다. 이 수는 1,000보다 작거나 같은 자연수이고, L은 50보다 작거나 같은 자연수이다. 그리고 중복되지 않는다

www.acmicpc.net

 

728x90
반응형

'Algorithm > Python' 카테고리의 다른 글

[BOJ]1992. 쿼드트리  (0) 2020.11.17
[BOJ]1041. 주사위  (0) 2020.11.12
[BOJ]10775. 공항  (0) 2020.10.29
[BOJ]1786. 찾기  (0) 2020.10.27
[BOJ]19948. 음유시인 영재  (0) 2020.10.15
728x90
반응형

문제:

오늘은 신승원의 생일이다.

박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다.

공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다.

공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다.

신승원은 가장 많은 비행기를 공항에 도킹시켜서 박승원을 행복하게 하고 싶어한다. 승원이는 비행기를 최대 몇 대 도킹시킬 수 있는가?

입력:

첫 번째 줄에는 게이트의 수 G (1 ≤ G ≤ 105)가 주어진다.

두 번째 줄에는 비행기의 수 P (1 ≤ P ≤ 105)가 주어진다.

이후 P개의 줄에 gi (1 ≤ gi ≤ G) 가 주어진다.

출력:

승원이가 도킹시킬 수 있는 최대의 비행기 수를 출력한다.

풀이방법:

유니온-파인드 알고리즘을 사용해서 문제를 풀려고 한다. 우선 초기 게이트들은 각자 번호로 초기화를 한다. 그리고 앞으로 들어오는 비행기를 게이트에 할당하기 시작한다. 이 때 할당하는 방법은 find()함수로 진행을 하며, 비행기의 번호에 따라 가장 큰 게이트에 도킹을 한다. 즉 gi번 비행기는 gi게이트에 할당하도록 하고, 만약 gi게이트에 이미 도킹 된 비행기가 있다면 그 전 게이트(gi-1)에 할당한다. 이렇게 계속해서 할당을 하다가 0번째 게이트를 만나게 되면 더 이상 도킹을 진행할 수 없기 때문에 공항을 폐쇄한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import sys
sys.setrecursionlimit(100000)
 
= int(input())
= int(input())
 
def find(v):
    if parent[v]==v:
        return v
    else:
        parent[v]=find(parent[v])
        return parent[v]
 
parent = [i for i in range(g+1)]
    
plane = []
for _ in range(p):
    plane.append(int(input()))
 
answer = 0
for p in plane:
    c = find(p)
    if c==0:
        break
    parent[c]=c-1
    answer+=1
print(answer)
cs

 

문제링크:

www.acmicpc.net/problem/10775

 

10775번: 공항

예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불

www.acmicpc.net

 

728x90
반응형

'Algorithm > Python' 카테고리의 다른 글

[BOJ]1041. 주사위  (0) 2020.11.12
[BOJ]1059. 수2  (0) 2020.11.10
[BOJ]1786. 찾기  (0) 2020.10.27
[BOJ]19948. 음유시인 영재  (0) 2020.10.15
[BOJ]1644. 소수의 연속합  (0) 2020.10.13

+ Recent posts