졍's 기술 블로그

가장 큰 증가 부분 수열

티어 : Silver 2
시간 제한 : 1 초
메모리 제한 : 256 MB
알고리즘 분류 : 다이나믹 프로그래밍

문제

수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 합이 가장 큰 증가 부분 수열의 합을 출력한다.

예제 입출력

Algorithm

Dynamic Programming
점화식 : dp[i] = max(dp[i], dp[j] + A[i])

Code

N = int(input())
A = [int(num) for num in input().split()]

dp = A[:]
dp[0] = A[0]
for i in range(1, N):
    for j in range(i):
        if A[j] < A[i]:
            dp[i] = max(dp[i], dp[j] + A[i])

print(max(dp))

메모리: 30840 KB
시간: 208 ms

도움받은 게시물

https://www.acmicpc.net/board/view/67313

포도주 시식

티어 : Silver 1
시간 제한 : 2 초
메모리 제한 : 128 MB
알고리즘 분류 : 다이나믹 프로그래밍

문제

효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.

1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오. 

예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.

입력

첫째 줄에 포도주 잔의 개수 n이 주어진다. (1 ≤ n ≤ 10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다.

출력

첫째 줄에 최대로 마실 수 있는 포도주의 양을 출력한다.

예제 입출력

Algorithm

Dynamic Programming
점화식
dp[3] = max(1 + 2, 2 + 3, 1 + 3)
dp[4] = max(1+2+4, 1+3+4, 1+2+3)
...
dp[n] = max(dp[n-3]+graph[n-1]+graph[n], dp[n-2]+graph[n], dp[n-1])

Code

n = int(input())
graph = [0]
for _ in range(n):
    graph.append(int(input()))

dp = [0] * (n+1)
dp[1] = graph[1]
if n > 1:
    dp[2] = graph[1] + graph[2]
if n > 2:
    dp[3] = max(dp[1] + graph[3], dp[2], graph[2] + graph[3])

for idx in range(4, n+1):
    dp[idx] = max(dp[idx-3] + graph[idx-1] + graph[idx], dp[idx-2] + graph[idx], dp[idx-1])
print(dp[-1])

메모리: 30840 KB
시간: 536 ms

도움받은 게시물

https://www.acmicpc.net/board/view/80678

스티커

티어 : Silver 1
시간 제한 : 1 초
메모리 제한 : 256 MB
알고리즘 분류 : 다이나믹 프로그래밍

문제

상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다.

상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다.

모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다. 먼저, 그림 (b)와 같이 각 스티커에 점수를 매겼다. 상냥이가 뗄 수 있는 스티커의 점수의 최댓값을 구하는 프로그램을 작성하시오. 즉, 2n개의 스티커 중에서 점수의 합이 최대가 되면서 서로 변을 공유 하지 않는 스티커 집합을 구해야 한다.

위의 그림의 경우에 점수가 50, 50, 100, 60인 스티커를 고르면, 점수는 260이 되고 이 것이 최대 점수이다. 가장 높은 점수를 가지는 두 스티커 (100과 70)은 변을 공유하기 때문에, 동시에 뗄 수 없다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 점수이다. 연속하는 두 정수 사이에는 빈 칸이 하나 있다. 점수는 0보다 크거나 같고, 100보다 작거나 같은 정수이다. 

출력

각 테스트 케이스 마다, 2n개의 스티커 중에서 두 변을 공유하지 않는 스티커 점수의 최댓값을 출력한다.

예제 입출력

Algorithm

Dynamic Programming
점화식
dp[i][j] = max(dp[x][y-1], dp[x+1][y-1] + graph[x][y]) (i == 0)
dp[i][j] = max(dp[x][y-1], dp[x-1][y-1] + graph[x][y]) (i == 1)

Code

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    n = int(input())
    graph = [list(map(int, input().split())) for _ in range(2)]
    
    dp = [[0 for _ in range(n)] for _ in range(2)]
    dp[0][0] = graph[0][0]
    dp[1][0] = graph[1][0]
    for y in range(1, n):
        for x in range(2):
            # x 가 0일 때
            if x == 0:
                dp[x][y] = max(dp[x][y-1], dp[x+1][y-1] + graph[x][y])
            else:
                dp[x][y] = max(dp[x][y-1], dp[x-1][y-1] + graph[x][y])
    print(max(dp[0][-1], dp[1][-1]))

메모리: 47620 KB
시간: 1232 ms

이친수

티어 : Silver 3
시간 제한 : 2 초
메모리 제한 : 128 MB
알고리즘 분류 : 다이나믹 프로그래밍

문제

0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.

1. 이친수는 0으로 시작하지 않는다.
2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.

예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.

N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다.

출력

첫째 줄에 N자리 이친수의 개수를 출력한다.

예제 입출력

Algorithm

Dynamic Programming
점화식 : dp[i] = dp[i-1] + dp[i-2]

Code

N = int(input())
dp = [0] * (N+1)
dp[1] = 1
if N > 1:
    dp[2] = 1
    
for idx in range(2, N+1):
    dp[idx] = dp[idx-1] + dp[idx-2]

print(dp[N])

메모리: 30840 KB
시간: 72 ms

오르막 수

티어 : Silver 1
시간 제한 : 1 초
메모리 제한 : 256 MB
알고리즘 분류 : 다이나믹 프로그래밍

문제

오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다.

예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다.

수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다.

입력

첫째 줄에 N (1 ≤ N ≤ 1,000)이 주어진다.

출력

첫째 줄에 길이가 N인 오르막 수의 개수를 10,007로 나눈 나머지를 출력한다.

예제 입출력

Algorithm

Dynamic Programming
점화식
dp[i][j] = dp[i][j-1] - dp[i-1][j-1] (j != 0)
dp[i][0] = sum(dp[i-1])

Code

N = int(input())
# dp table 초기화
dp = [[0 for _ in range(10)] for _ in range(N+1)]
dp[1] = [1] * 10

num = 0
for i in range(2, N+1):
    for j in range(10):
        if j == 0:
            dp[i][0] = sum(dp[i-1])
        else:
            dp[i][j] = dp[i][j-1] - dp[i-1][j-1]
            
print(sum(dp[N]) % 10007)

메모리: 30840 KB
시간: 76 ms

쉬운 계단 수

티어 : Silver 1
시간 제한 : 1 초
메모리 제한 : 256 MB
알고리즘 분류 : 다이나믹 프로그래밍

문제

45656이란 수를 보자.

이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

입력

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

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

예제 입출력

Algorithm

Dynamic Programming
i : 숫자 자릿수, j : j로 시작하는 숫자의 개수
dp[i][j] = dp[i-1][1] (j == 0)
dp[i][j] = dp[i-1][8] (j == 9)
dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] (j != 0, j != 9)

Code

N = int(input())
dp = [[0 for _ in range(10)] for _ in range(N+1)]
dp[1] = [1 for _ in range(10)]

for i in range(2, N+1):
    for j in range(10):
        # j가 0이면 1로 변경
        if j == 0:
            dp[i][j] = dp[i-1][1]
        # j가 9이면 i-1의 j-1의 값과 동일
        elif j == 9:
            dp[i][j] = dp[i-1][8]
        # 그 외의 경우
        else:
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

print((sum(dp[N])-dp[N][0])%1000000000)

메모리: 30840 KB
시간: 76 ms

A→B

티어 : Silver 1
시간 제한 : 2 초
메모리 제한 : 512 MB
알고리즘 분류 : 그래프 이론, 그리디 알고리즘, 그래프 탐색, 너비 우선 탐색

문제

정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.

• 2를 곱한다.
• 1을 수의 가장 오른쪽에 추가한다. 

A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

입력

첫째 줄에 A, B (

)가 주어진다.

출력

A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.

예제 입출력

Algorithm

Greedy
1. B가 2로 나누어 떨어지면 2로 나누기
2. 그렇지 않고 마지막 숫자가 1이면 1 빼기
3. 마지막 숫자가 1이 아니면 -1 출력
4. A가 만들어지면 횟수 출력
5. A보다 작아지면 -1 출력

Code

A, B = map(int, input().split())
answer = 0
while True:
    # B가 2로 나누어 떨어지면 2로 나누기
    if B % 2 == 0:
        B //= 2
        answer += 1
    # B가 2로 나누어 떨어지지 않고 마지막 숫자가 1이면 1 빼기
    elif str(B)[-1] == '1':
        B = int(str(B)[:-1])
        answer += 1
    # B가 2로 나누어 떨어지지 않고 마지막 숫자가 1이 아니면 -1 출력
    else:
        print(-1)
        break
    
    # B가 A보다 작아지면 -1 출력
    if A > B:
        print(-1)
        break
    # A가 만들어지면 횟수 출력
    elif A == B:
        print(answer+1)
        break

메모리: 30840 KB
시간: 72 ms

상근이의 여행

티어 : Silver 3
시간 제한 : 1 초
메모리 제한 : 256 MB
알고리즘 분류 : 그래프 이론, 트리

문제

상근이는 겨울방학을 맞아 N개국을 여행하면서 자아를 찾기로 마음먹었다.

하지만 상근이는 새로운 비행기를 무서워하기 때문에, 최대한 적은 종류의 비행기를 타고 국가들을 이동하려고 한다.

이번 방학 동안의 비행 스케줄이 주어졌을 때, 상근이가 가장 적은 종류의 비행기를 타고 모든 국가들을 여행할 수 있도록 도와주자.

상근이가 한 국가에서 다른 국가로 이동할 때 다른 국가를 거쳐 가도(심지어 이미 방문한 국가라도) 된다.

입력

첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고,

각 테스트 케이스마다 다음과 같은 정보가 주어진다.

• 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 주어진다.
• 이후 M개의 줄에 a와 b 쌍들이 입력된다. a와 b를 왕복하는 비행기가 있다는 것을 의미한다. (1 ≤ a, b ≤ n; a ≠ b) 
• 주어지는 비행 스케줄은 항상 연결 그래프를 이룬다.

출력

테스트 케이스마다 한 줄을 출력한다.

• 상근이가 모든 국가를 여행하기 위해 타야 하는 비행기 종류의 최소 개수를 출력한다.

예제 입출력

Algorithm

DFS
1. 그래프 구현 (단방향)
2. DFS 돌면서 몇 개의 간선이 있는지 확인

Code

import sys
input = sys.stdin.readline

def dfs(country):
    global answer # 간선 개수
    
    # 방문한 기록 있으면 return
    if visited[country]:
        return
    
    # 방문 기록
    visited[country] = True
    answer += 1
    
    # 인접 국가 여행
    for next_country in graph[country]:
        dfs(next_country)

T = int(input())
for _ in range(T):
    N, M = map(int, input().split())
    answer = -1
    visited = [False for _ in range(N+1)]
    
    # graph 구현
    graph = [[] for _ in range(N+1)]
    for _ in range(M):
        a, b = map(int, input().split())
        graph[a].append(b)

    # dfs 돌면서 간선 개수 확인
    for country in range(1, N+1):
        # 방문하지 않은 국가만 확인
        if not visited[country]:
            dfs(country)
    
    print(answer)

메모리: 31216 KB
시간: 228 ms