졍's 기술 블로그

가장 긴 바이토닉 부분 수열

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

문제

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만,  {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.

수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

입력

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

출력

첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

예제 입출력

Algorithm

Dynamic Programming
1. 최장 증가수열 구하기
2. 최장 감소수열 구하기
3. 최장 증가수열 + 최장 감소수열의 최댓값 - 1 출력

Code

import sys
input = sys.stdin.readline

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

lis = [1] * N # 최장 증가 수열
lds = [1] * N # 최장 감소 수열

# 최장 증가수열 구하기
for i in range(1, N):
    for j in range(i):
        if A[j] < A[i]:
            lis[i] = max(lis[i], lis[j] + 1)
            
# 최장 감소수열 구하기
A.reverse()
for i in range(1, N):
    for j in range(i):
        if A[j] < A[i]:
            lds[i] = max(lds[i], lds[j] + 1)

# lis와 lds의 합의 최댓값 - 1
lds.reverse()
dp = []
for idx in range(N):
    dp.append(lis[idx] + lds[idx])
print(max(dp) - 1)

메모리: 30840 KB
시간: 344 ms

가장 큰 증가 부분 수열

티어 : 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

안전 영역

티어 : Silver 1
시간 제한 : 1 초
메모리 제한 : 128 MB
알고리즘 분류 : 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

문제

재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다.

어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어지며 배열의 각 원소는 해당 지점의 높이를 표시하는 자연수이다. 예를 들어, 다음은 N=5인 지역의 높이 정보이다.

이제 위와 같은 지역에 많은 비가 내려서 높이가 4 이하인 모든 지점이 물에 잠겼다고 하자. 이 경우에 물에 잠기는 지점을 회색으로 표시하면 다음과 같다. 

물에 잠기지 않는 안전한 영역이라 함은 물에 잠기지 않는 지점들이 위, 아래, 오른쪽 혹은 왼쪽으로 인접해 있으며 그 크기가 최대인 영역을 말한다. 위의 경우에서 물에 잠기지 않는 안전한 영역은 5개가 된다(꼭짓점으로만 붙어 있는 두 지점은 인접하지 않는다고 취급한다). 

또한 위와 같은 지역에서 높이가 6이하인 지점을 모두 잠기게 만드는 많은 비가 내리면 물에 잠기지 않는 안전한 영역은 아래 그림에서와 같이 네 개가 됨을 확인할 수 있다. 

이와 같이 장마철에 내리는 비의 양에 따라서 물에 잠기지 않는 안전한 영역의 개수는 다르게 된다. 위의 예와 같은 지역에서 내리는 비의 양에 따른 모든 경우를 다 조사해 보면 물에 잠기지 않는 안전한 영역의 개수 중에서 최대인 경우는 5임을 알 수 있다. 

어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산하는 프로그램을 작성하시오. 

입력

첫째 줄에는 어떤 지역을 나타내는 2차원 배열의 행과 열의 개수를 나타내는 수 N이 입력된다. N은 2 이상 100 이하의 정수이다. 둘째 줄부터 N개의 각 줄에는 2차원 배열의 첫 번째 행부터 N번째 행까지 순서대로 한 행씩 높이 정보가 입력된다. 각 줄에는 각 행의 첫 번째 열부터 N번째 열까지 N개의 높이 정보를 나타내는 자연수가 빈 칸을 사이에 두고 입력된다. 높이는 1이상 100 이하의 정수이다.

출력

첫째 줄에 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력한다.

예제 입출력

Algorithm

DFS
1. 높이 정보 그래프 구현
2. dfs를 이용해 잠기지 않는 지역의 덩어리 구하기
3. 최댓값 출력

Code

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

def dfs(x, y, amount_of_rain):
    
    # 위치를 벗어나면 return
    if x < 0 or x > N-1 or y < 0 or y > N-1:
        return False
    
    # 방문한 기록 있거나 높이가 비의 양보다 작거나 같으면 return
    if visited[x][y] or height_info[x][y] <= amount_of_rain:
        return False
    
    # 방문 기록
    visited[x][y] = True
    
    # 주변 노드 방문
    for dx, dy in dir:
        dfs(x+dx, y+dy, amount_of_rain)
    
    return True

N = int(input())
height_info = [list(map(int, input().split())) for _ in range(N)]

# 상, 하, 좌, 우
dir = [(-1, 0), (1, 0), (0, -1), (0, 1)]

# height_info의 최댓값 찾기
max_ = 0
for i in range(N):
    max_ = max(max_, max(height_info[i]))

answer = 0
for amount_of_rain in range(max_+1):
    count = 0 # 덩어리 개수
    visited = [[False for _ in range(N)] for _ in range(N)]
    
    # dfs 돌면서 비의 양보다 높은 곳만 접근했을 때의 덩어리 개수 구하기
    for x in range(len(height_info)):
        for y in range(len(height_info[i])):
            if dfs(x, y, amount_of_rain):
                count += 1
    answer = max(answer, count)

print(answer)

메모리: 40748 KB
시간: 1684 ms