Jenikeju

문제

오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.

파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.

N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.

내가 푼 풀이

- P(1) = 1, P(2) = 1, P(3) = 1, P(n) = P(n-2) + P(n-3) 임을 알수있다. (n > 3) 

- 해당 점화식을 넣어서 P(N)값 출력

import Foundation

let count = Int(String(readLine()!))!

for i in 0..<count {
    let num = Int(String(readLine()!))!
    var dp = Array(repeating: 0, count: num+1)
    
    if num <= 3 {
        dp[num] = 1
        print(dp[num])
    } else {
        for i in 1...num {
            if i <= 3 {
                dp[i] = 1
                continue
            }
            dp[i] = dp[i-2] + dp[i-3]
        }
        print(dp[num])
    }

}

import Foundation

var count = Int(String(readLine()!))!
var dp = Array(repeating: 0, count: count)
var arr = readLine()!.split(separator: " ").map{ Int(String($0))!}

for i in 0..<count {
    if i == 0 {
        dp[i] = arr[0]
        continue
    }
    dp[i] = max(arr[i], dp[i-1] + arr[i])
}
print(dp.max()!)

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

내가 푼 풀이

- 첫번째인덱스와 마지막 인덱스는 선택지 없이 위에 있는 수를 더해야한다.

- 중간에 있는 인덱스 i 는 i-1 과 i중 최댓값을 더하면된다.

- arr[i] = max(dp[i-1], dp[i]) + arr[i]

- arr[0] = dp[0] + arr[0]

- arr[arr.count-1] = dp[arr.count-2] + arr[arr.count-1]

- dp[0...i] = arr[0...i] , dp에 arr값을 넣어준다.

- dp의 최댓값 출력

import Foundation

var count = Int(String(readLine()!))!
var dp = Array(repeating: 0, count: count)

for i in 0..<count {
    var arr = readLine()!.split(separator: " ").map{ Int(String($0))!}
    
    if i == 0 {
        dp[0] = arr[0]
        continue
    }
    for j in 0...i {
        if j == 0 {
            arr[0] = arr[0] + dp[0]
        } else if j == i {
            arr[j] = dp[i-1] + arr[j]
        } else {
            arr[j] = arr[j] + max(dp[j-1], dp[j])
        }
    }
    for k in 0..<arr.count {
        dp[k] = arr[k]
    }
    
}

print(dp.max()!)

내가 푼 풀이

- 처음에는 문제를 잘 이해못해서 받은 수열을 set으로 바꿔서 count 출력 하면 되는거 아닌가 했는데, 수열 순서대로 부분수열의 갯수를 구하는것이였다.

- arr = [10, 11, 9]  Set(arr).count = 3, 부분 수열의 최대 길이: [10,11] = 2

- dp를 수열의 크기+1 만큼 만들어서 해당 숫자가 이미 나와있는 수열의 몇번째인지 저장한다.

arr = [0, 10, 20, 10, 30, 20, 50]

• dp[1] = 1 
• dp[2] : arr[2] = 20 , 20보다 작은수 10 ---> dp[2] = 2
• dp[3] : arr[3] = 10 , 10보다 작은수는 없다. ---> 증가하는 수열의 첫번째다. dp[3] = 1
• dp[4] : arr[4] = 30 , 40보다 작은수 10, 20, 10 ---> max(dp[1], dp[2], dp[3]) + 1 , dp[4] = 3

import Foundation

var count = Int(String(readLine()!))!
var arr = [0] + readLine()!.split(separator: " ").map{ Int(String($0))!}
var dp = Array(repeating: 0, count: count+1)

dp[1] = 1
if count == 1 {
    print(dp[1])
} else {
    for i in 2...count {
        var check = [Int]()
        for j in 1..<i {
            if arr[i] > arr[j] {
                check.append(dp[j])
            }
        }
        if check.isEmpty {
            dp[i] += 1
        } else {
            dp[i] = check.max()! + 1
        }
    }
    print(dp.max()!)
}

문제

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.

예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.

계단 오르는 데는 다음과 같은 규칙이 있다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

- dp문제로 점화식을 찾는데 애먹었다.

- 다음 규칙중 3번이 중요했다. 마지막 계단을 반드시 밟아야한다.

- 마지막 계단 n 을 밟는경우 두가지

• 바로 직전 계단을 밟는 경우: n, n-1, n-3 번째 계단을 밟는다.
• 2칸뛰어서 마지막 계단을 밟는경우: n, n-2번째 계단을 밟는다.

위 두가지를 점화식으로 나타낸다. ( points, dp, i는 순번 )

1. dp[n] = dp[n-3] + points[n-1] + points[n]

2. dp[n] = dp[i-2] + points[n]

--> dp[n] = max(points[n-1] + dp[n-3], dp[n-2]) + points[n]

import Foundation

var count = Int(String(readLine()!))!
var points = Array(repeating: 0, count: count+1)
var dp = Array(repeating: 0, count: count+1)

for i in 1...count {
    points[i] = Int(String(readLine()!))!
}

dp[1] = points[1]

if count == 1 {
    print(dp[1])
} else if count == 2 {
    dp[2] = max(points[1] + points[2], points[2])
    print(dp[2])
} else {
    dp[2] = max(points[1] + points[2], points[2])
    for i in 3...count {
        dp[i] = max(points[i-1] + dp[i-3], dp[i-2]) + points[i]
    }
    print(dp[count])
}

내가 푼 풀이

- 집의 갯수가 주어지고 각 줄은 빨강, 초록, 파랑의 색칠비용이 주어진다.

- 규칙에 따르면 결국 인접한 집의 색은 서로 다른색이여야 한다는 것이다.

- 각 줄의 최솟값을 찾아 따라가면, 같은 색을 칠할 경우가 생긴다.

- 집의 갯수가 2개 이상이니,  집을 색칠할 색을 정하고, 그 전에 있는 집의 칠할 수 있는 색의 최솟값을 더하는 식으로 접근했다.

- 위 접근을 점화식으로 표현해본다.

• arr = [R, G, B] , count = 집의 갯수
• dp = Array(repeating: Array(repeating: 0, count: 3), count: count+1)
• dp[n][0] = min(dp[n-1][1], dp[n-1][2]) + arr[0]
• dp[n][1] = min(dp[n-1][0], dp[n-1][2]) + arr[1]
• dp[n][2] = min(dp[n-1][1], dp[n-1][0]) + arr[2]

-> dp[0][0] = 첫번째 집 빨강색비용,  dp[0][1] = 첫번째 집 파랑색비용, dp[0][2] = 첫번째 집 초록비용, 

-> n번째를 빨강으로 칠한다면, n-1번째 집의 파랑,초록 의 최솟값 + n번째 빨강비용

-> 규칙에 따른 모든 집 색칠 비용의 최솟값은 dp[n]의 최솟값이다.

import Foundation

var count = Int(String(readLine()!))!
var dp = Array(repeating: Array(repeating: 0, count: 3), count: count+1)

for i in 1...count {
    var arr = readLine()!.split(separator: " ").map{ Int(String($0))!}

    if i == 1 {
        dp[1] = [arr[0], arr[1], arr[2]]
        continue
    }
    dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + arr[0]
    dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + arr[1]
    dp[i][2] = min(dp[i-1][1], dp[i-1][0]) + arr[2]
}

print(dp[count].min()!)

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

내가 푼 풀이

- n이 5일때까지 경우의 수를 구해봤는데 결국 피보나치 수열을 구하는 식이 나온다.

- f(n) = f(n-1) + f(n-2) 

- n이 일정숫자를 넘으면 담을수없이 커진다. 그래서 계산할때마다 10007로 나눈 나머지를 넣는다.

- f(n) % 10007 = ( f(n-1) + f(n-2) ) % 10007

import Foundation

var num = Int(String(readLine()!))!
var dp = Array(repeating: 0, count: 1001)
dp[1] = 1
dp[2] = 2
if num < 3 {
    print(dp[num])
} else {
    for i in 3...num {
        dp[i] = (dp[i-1] + dp[i-2]) % 10007
    }
    print(dp[num])
}

int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

내가 푼 풀이

- 정수 n이 주어지면 fibonacci(n) 의 f(0)과 f(1)의 호출횟수를 구하는 문제다.

- f(n) = f(n-1) + f(n-2) 이므로 정수 N부터 1까지 내려오면서 횟수를 더해주면 된다.

- 결과는 dp[0] dp[1] 의 원소값

import Foundation

var count = Int(String(readLine()!))!

for i in 0..<count {
    var num = Int(String(readLine()!))!
    var arr = Array(repeating: 0, count: num+1)
    
    if num == 0 {
        arr[0] = 1
        print("1 0")
        continue
    } else if num == 1 {
        arr[1] = 1
        print("\(arr[0]) \(arr[1])")
        continue
    }
    arr[num] = 1
    for i in stride(from: num, to: 1, by: -1) {
        arr[i-1] += arr[i] * 1
        arr[i-2] += arr[i] * 1
    }
    print("\(arr[0]) \(arr[1])")
}