AndroidTeacher

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

문제 설명

N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오.

(x, y)는 x행 y열을 의미한다.

예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.

여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.

표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.

풀이 과정

이 문제는 누적 합 으로 해결할 수 있다.

다음과 같은 표가 있다고 하자.

이제 표의 각각의 칸에는 그 칸까지의 누적합을 작성하자.

예를 들어, (2,2)에는 (0,0) ~ (2,2) 까지의 합을 더한 값이 들어간다.

누적합으로 작성한 표는 다음과 같다.

이 때, (1, 1) ~ (2, 2) 의 합계를 구하고 싶다면

(2,2)에 저장된 누적합에

(1,1)에 저장된 누적합을 빼주고

겹치는 부분인 (1,1)의 값(누적합이 아닌 고유의 그 값)을 더해주면 된다.

(1,1)칸은 두 번 뺐기 때문에 한 번 더해주어야 하는 것이다.

이를 파이썬 코드로 나타내면 다음과 같다.

import sys

input = sys.stdin.readline
n, m = map(int, input().split())

graph = []

for i in range(n):
  graph.append(list(map(int, input().split())))

acc = [[0]*(n+1) for _ in range(n+1)]

for i in range(1, n+1):
  for j in range(1, n+1):
    acc[i][j] = acc[i-1][j] + acc[i][j-1] - acc[i-1][j-1] + graph[i-1][j-1]

print(acc)

for i in range(m):
  x1,y1,x2,y2 = map(int, input().split())

  print(acc[x2][y2] - acc[x1-1][y2] - acc[x2][y1-1] + acc[x1-1][y1-1])

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

문제 설명

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

자세한 문제 설명은 위 링크를 참고하시길 바랍니다.

풀이 과정

이 문제는 DP(다이나믹 프로그래밍)을 이용해 최대 증가 수열을 찾는 문제라고 할 수 있다.

전깃줄이 교차하지 않도록 하려면 어떻게 해야할지에 대해 먼저 생각해보자.

먼저, 위 그림에서 A의 1번과 B의 8번만 연결되어 있다고 가정해보자.

그리고 이 때, 아래의 ①번 상황과 ②번 상황을 각각 생각해보자.

① A의 2번과 B의 2번이 연결된다면 교차하게 된다. ( 1 - 8 / 2 - 2 )

② A의 3번과 B의 9번이 연결된다면 서로 교차하지 않는다. ( 1 - 8 / 3 - 9 )

위의 예시를 보면 다음과 같음을 알 수 있다.

전깃줄 두 개가 있을 때, A의 번호가 작은 순서대로 정렬을 하여 첫 번째, 두 번째 전깃줄이라고 순서를 매긴다면

두 번째 전깃줄의 B번호가 첫 번째 전깃줄의 B번호보다 작다면 교차하게 된다.

하지만 두 번째 전깃줄의 B번호가 첫 번째 전깃줄의 B번호보다 크거나 같으면 교차하지 않게 된다.

이를 그대로 연장하여 전깃줄 세개인 상황을 만들면

세 번째 전깃줄의 B번호가 앞의 두개의 전깃줄의 B번호보다 작다면 교차함을 알 수 있다.

즉, 우리가 원하는 그림은 다음과 같음을 알 수 있다.

이런 그림이 탄생하면 전깃줄이 서로 교차하지 않게 된다.

그래서 먼저,

① A의 번호가 작은 순서대로 정렬을 하고

② 앞순서의 B가 뒷순서의 B보다 작은 경우가 최대로 이어지는 경우를 찾는다.

이렇게 접근을 하기 위해 DP를 이용하면 된다.

앞순서의 B가 뒷순서의 B보다 작은 경우에만 DP 카운팅을 늘려서

최종적으로 최대의 DP카운트를 찾으면 정답을 찾게 된다.

이 때, 최대 연장부분을 찾기 위해서는 앞에서부터 하나씩 검사를 해야 하기 때문에

2중 for문을 이용해 DP를 갱신하였다.

이를 반영한 파이썬 코드는 다음과 같다.

n = int(input())
lists = []
dp = [1]*n

for i in range(n):
  a, b = map(int, input().split())
  lists.append([a, b])

lists.sort()

for i in range(1, n):
  for j in range(0, i):
    if lists[j][1] < lists[i][1]:
      dp[i] = max(dp[i], dp[j]+1)
      
print(n-max(dp))

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

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

문제 설명

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

풀이 과정

이 문제는 DP(다이나믹 프로그래밍)을 이용해 최댓값을 찾는 문제이다.

DP라는 리스트(배열)의 각 칸에는 그 칸까지 숫자들을 고려했을 때의 연속합의 최댓값을 담을 것이다.

예를 들어, DP[2]는 2번째 인덱스 까지의 숫자를 고려했을 때의 최댓값이 저장될 것이다.

이 때, 만약 이전 인덱스 까지의 연속합이 음수라서 이전까지의 합에 현재 수를 더하는 것 보다

현재 수 만을 갖고있는게 더 큰 경우에는

이전까지 연속합을 끊어내고 현재 인덱스부터 새로운 구간합을 만들어가야 한다.

이러한 부분들을 고려하여 작성한 파이썬 코드는 다음과 같다.

n = int(input())
nums = list(map(int, input().split()))

INF = -int(1e9)
dp = [INF]*n

if n<2:
  dp[0] = nums[0]

else:
  dp[0] = nums[0]
  dp[1] = max(nums[1], dp[0]+nums[1])
  for i in range(2, n):
    dp[i] = max(dp[i-1]+nums[i], nums[i])

print(max(dp))

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

문제 설명

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

수열 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가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

풀이 과정

이 문제는 이 문제의 하위버전인 가장 긴 증가하는 부분수열 문제(https://www.acmicpc.net/problem/11053)를 풀었다면 쉽게 접근할 수 있는 문제이다.

먼저, 길이 10짜리 수열을 보자.

1 5 2 1 4 3 4 5 2 1

일단은, 감소하는 부분은 생각하지 말고 인덱스별로 증가하는 부분만을 생각해보자.

5는 1 -> 5 로 증가하기 때문에 길이 2짜리 부분수열이며

2는 1 -> 5 -> 2 가 될 수 없기 때문에 1 -> 2 로 2이다.

1은 증가할 수 없기 때문에 1이며

4는 1 -> 2 -> 4 이기 때문에 3이다.

이러한 식으로 부분증가 수열 중 최대 길이를 찾아내야 하는데,

이는 기준점(i)을 2번째 인덱스부터 끝점까지 반복문을 통해 이동해주며

그 안에서의 다른 기준점(j)을 세워 처음부터 i번째 인덱스 이전까지 돌며

i번째 수보다 작은 수를 만났을 경우에 그 수까지 부분수열의 길이에 +1을 해주면 된다.

즉, 2중 for문을 통해 i번째 인덱스에 대해 그 인덱스의 부분수열을 구해주면 된다.

참고로, 배열 길이는 1000이므로 2중 for문을 돌더라도 시간초과가 발생하지 않는다.

이를 그대로, 감소하는 수열에 적용해보자.

이번엔 기준점(i)을 처음 2번째 인덱스가 아닌 마지막에서 2번째 인덱스를 두어 감소하도록 하고

그 안의 기준점(j)을 끝점부터 i번째 인덱스 까지 돌며

i번째 수보다 작은 수를 만났을 경우에 그 수까지의 부분수열의 길이에 +1을 해주면 된다.

이를 코틀린 코드로 나타내면 다음과 같다.

import kotlin.collections.*
import kotlin.math.max

fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    val list = readLine()!!.split(" ").map { it.toInt() }

    val upDp = Array(1001){1}
    val downDp = Array(1001){1}

    for(i in 1 until n) {
        for(j in 0 until i) {
            if(list[i] > list[j]) {
                upDp[i] = max(upDp[i], upDp[j] + 1)
            }
        }

    }

    for(i in n-2 downTo 0) {
        for(j in n-1 downTo i+1) {
            if(list[i] > list[j]) {
                downDp[i] = max(downDp[i], downDp[j] + 1)
            }
        }
    }

    var max = 0
    for(i in 0 until n) {
       if(upDp[i] + downDp[i] > max) {
           max = upDp[i] + downDp[i]
       }
    }

    print(max-1)
}

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

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

문제 설명

5656이란 수를 보자.

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

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

풀이 과정

이 문제는 단계마다의 규칙을 찾아 점화식을 세워 구현하는 DP 문제이다.

길이 1짜리 계단을 생각해보면,

1 2 3 4 5 6 7 8 9 총 9개의 계단이 있다.

길이 2짜리 계단을 생각해보면,

10 12 21 23 32 34 43 45 ... 87 89 98 로 총 17개가 있다.

그렇다면 길이 3짜리 계단은,

101 121 123 212 210 232 234 ... 789 787 898 987 989 가 있다.

여기서 규칙을 찾아보자.

끝자리가 0이나 9라면 더 늘릴 수 있는 수가 없기 때문에 하나만 더 추가로 만들 수 있다.

예를 들어, 10 같은 경우 끝자리 0에 1을 추가한 101 만을 만들 수 있다.

하지만, 끝자리가 0이 아닌 21 같은 경우는 1을 추가한 212나 1을 뺀 210을 만들 수 있게 된다.

이를 이용하면, 다음과 같은 코드를 작성할 수 있다.

fun main(args: Array<String>) {
    val n = readLine()!!.toInt()

    val dp = Array(101) { IntArray(10) }
    dp[1][0] = 0
    for(i in 1 until 10) {
        dp[1][i] = 1
    }

    for(i in 2 until n+1) {
        for(j in 0 until 10) {
            when(j) {
                0 -> dp[i][j] = dp[i-1][1]
                9 -> dp[i][j] = dp[i-1][8]
                else -> dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % 1000000000
            }
        }
    }

    var ans = 0L
    dp[n].forEach { ans += it }
    print(ans%1000000000)

}

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

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

문제 설명

위 링크에 주어진 문제 설명처럼, 계단을 오르는 문제이다.

단, 3번 연속된 계단을 이어서 오를 수는 없으며

마지막 계단은 무조건 밟아야 한다.

풀이 과정

이 문제는 DP(다이나믹 프로그래밍)을 이용해 앞에서 부터 최대값을 저장해 나가야 한다.

현재 계단을 밟는다면, 이전과 이이전을 연속해서 밟으면 안된다.

따라서, 현재 계단의 최댓값은 현재 + 이전 + 이이이전 or 현재 + 이이전 중에 선택을 해야한다.

한 가지 주의해야 할 점은,

인덱스 에러가 나지 않도록 하기 위해

n = 1일때, 2일때, 3 이상일 때의 케이스를 나눠주자.

n = int(input())
stairs = []
dp = [0]*301
for i in range(n):
    stairs.append(int(input()))

if n > 2:
    dp[0] = stairs[0]
    dp[1] = stairs[0]+stairs[1]
    dp[2] = max(stairs[0] + stairs[2], stairs[1]+stairs[2])
elif n > 1:
    dp[0] = stairs[0]
    dp[1] = stairs[0] + stairs[1]
elif n == 1:
    dp[0] = stairs[0]

for i in range(3, n):
    dp[i] = max(stairs[i] + stairs[i-1] + dp[i-3], stairs[i]+ dp[i-2])

print(dp[n-1])

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

문제 설명

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

주어진 그림처럼 삼각형 모양으로 숫자가 주어진다.

맨 위부터 시작해 제일 아래쪽으로 탐색을 하게되는데,

현재 지점에서 다음 지점(아래 지점)으로 이동할 때는, 왼쪽대각선과 오른쪽 대각선으로만 갈 수 있다.

이 방법으로 탐색했을 때, 탐색경로에 있는 숫자들을 모두 더했을 때의 최대가 되는 경로를 구하는 문제이다.

풀이 과정

이 문제는 DP(다이나믹 프로그래밍)을 이용해 앞에서부터 최댓값을 저장해나가며 푸는 문제이다.

가장 첫번째 열에 있는 숫자(7, 3, 8, 2, 4)들은 선택의 여지 없이 이전의 가장 왼쪽 수를 선택해야 한다.

예를 들어, 3번째 줄의 가장 왼쪽 숫자인 8은 2번째 줄의 3을 선택했을 때의 경로를 따라야 하며

4번째 줄의 가장 왼쪽 숫자인 2는 3번째 줄의 8을 선택했을 때의 경로를 따라야 한다.

그 이외의 숫자들은 이전(위) 숫자 두개 중 최댓값을 선택할 수 있다.

이러한 특징을 반영하여 DP배열을 2차원으로 만들어 아래와 같은 코드를 짤 수 있다.

DP[1][0]에는 1번째 줄의 0번째 수를 선택했을 때의 최댓값을 저장하고

DP[1][1]에는 1번째 줄의 1번째 수를 선택했을 때의 최댓값을 저장한다.

이를 파이썬 코드로 나타내면 다음과 같다.

n = int(input())

arr = []
dp = [[0]*n for _ in range(n)]
for i in range(n):
    arr.append(list(map(int, input().split())))

dp[0][0] = arr[0][0]

for i in range(1, n):
    for j in range(0, i+1):
        if j == 0:
            dp[i][j] = dp[i-1][j] + arr[i][j]
        else:
            dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + arr[i][j]

print(max(dp[n-1]))

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

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

문제 설명

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

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

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

풀이 과정

이 문제는 DP(다이나믹 프로그래밍)을 이용해 앞에서 부터 최소값을 저장해 나가며

모든 집을 칠했을 때의 최소값을 구하는 문제이다.

먼저 Nx3 모양의 2차원 DP배열을 만들어

R, G, B 페인트를 칠했을 때의 최솟값들을 저장해주자.

예를 들어, DP[N][0]은 현재 N번집에 R 페인트를 칠했을 때의 최솟값을 저장하게 된다.

첫 집은 R, G, B 모두를 선택할 수 있으므로

DP[0][0]에는 첫 번째 집의 R비용을,

DP[0][1]에는 첫 번째 집의 G비용을,

DP[0][2]에는 첫 번째 집의 B비용을 각각 저장하자.

두 번째 집부터, 바로 전집과는 다른 색을 칠해야 하므로

두번째 집에 R을 선택했다면 이전집에서는 G,B 를 칠한 것 중 최솟값을 선택하여 더하면 된다.

이러한 방식으로 값을 누적해나가 마지막 집의 DP값을 구하면 답을 구할 수 있다.

n = int(input())

cost = []
minCost = -int(1e9)
dp = [[0]*3 for _ in range(n)]
for i in range(n):
    cost.append(list(map(int, input().split())))

dp[0][0], dp[0][1], dp[0][2] = cost[0][0], cost[0][1], cost[0][2]

for i in range(1, n):
    dp[i][0] = min(dp[i-1][1] + cost[i][0], dp[i-1][2] + cost[i][0])
    dp[i][1] = min(dp[i-1][0] + cost[i][1], dp[i-1][2] + cost[i][1])
    dp[i][2] = min(dp[i-1][0] + cost[i][2], dp[i-1][1] + cost[i][2])

print(min(dp[n-1][0], dp[n-1][1], dp[n-1][2]))

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !