BOJ 가장긴증가하는부분수열, RGB거리

DP 문제가 유독 풀기가 힘들어서 이겨내기 위해 2문제를 골랐다. 

1. BOJ 11053 (가장 긴 증가하는 부분 수열)

난이도 : 실버2
DP 중에 유명한 예시인 LIS 유형이다. 

https://www.acmicpc.net/problem/11053

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

코드

N = int(input())
arr = list(map(int, input().split()))
d = [1 for _ in range(N)]
 
for i in range(N):
    for j in range(0, i):
        if arr[i]>arr[j]:
            d[i] = max(d[j]+1, d[i])
 
print(max(d))

설명

N = 6
arr = 10 20 10 30 20 50
d   = [1,  2,  1,  3,  2,  4]

arr 리스트를 돌면서, arr[0]~[i-1] 값과 arr[i] 값을 비교하여 만약 arr[i]가 더 크다면, d[j]+1 과 d[i] 중 더 큰 값을 저장한다. 

더 효율적으로 푸는 방법이 있을지 궁금하다. 

 

2. BOJ 1149 (RGB거리) (작성중)

난이도 : 실버1

https://www.acmicpc.net/problem/1149

스승님이 DP문제 중에 추천해줬던 기억이 있다. 너무 어려워서 손도 못댔었다...(^^*) 다시봐도 계속 뭐지..? 했었는데 알고보니 진짜 깔끔하게 풀리는 문제였다. 

문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

코드

N = int(input())
arr = []
for i in range(N):
    arr.append(list(map(int, input().split())))
 
for i in range(1, N):
    arr[i][0] += min(arr[i-1][1], arr[i-1][2])
    arr[i][1] += min(arr[i-1][0], arr[i-1][2])
    arr[i][2] += min(arr[i-1][0], arr[i-1][1])
print(min(arr[-1]))

설명

여기서 중요한 문제는 우리 집 색깔을 앞 집과 다르게 칠하는 것이다. 

          R   G   B
arr = [[26, 40, 83] 
        [49, 60, 57]
        [13, 89, 99]] 에서 arr[i][0]는 a[i-1][0] (같은 색상)를 제외하고 나머지 두 값 중 작은 값을 취해서 arr[i][0]과 더한다. 

arr = [[26, 40, 83] 
        [89, 86, 83]
        [96, 172, 185]]