Jenikeju

내가 푼 풀이

- N이 주어졌을때, 0부터 N까지 k번을 더해서 N을 만드는 경우의 수를 구한다.

- K = 1 인경우, 한번만 더해서 N을 만드려면 N 자기 자신을 더하는 방법 1가지다.

- K = 2 인경우, 두번 더해서 N을 만드려면 , 0 + N , 1 + (N-1), ... , N + 0 으로 N가지이다.

- 이를 "dp[n][k] = 0부터N까지의 정수 K번 더해서 합이 N이되는 경우의수" 로 정의하자.

- K = 1 인경우 자기 자신만 더하면 되므로 dp[n][1] = 1

- K = 2 인경우 자기 자신을 1씩차감한만큼 더해주면 되므로, dp[n][2] = n 이된다.

- 이제 K = 3 부터는 이전의 값을 저장된 값을 사용하려한다.

- 3번 더해서 N을 만드는 경우의 수를 초기값이 0부터 N까지의 경우의수를 생각해보자.

예시로 N = 3 , K = 3 일때

• 초기값 = 0 이라면, 나머지 3, 두번을 더해서 3을 만들때 => dp[3][2]
• 초기값 = 1 이라면, 나머지 2, 두번을 더해서 3을만들때 => dp[2][2]
• 초기값 = 2 이라면, 나머지 1, 두번을 더해서 3을 만들때 => dp[1][2]
• 초기값 = 3 이라면 나머지 0, 두번을 더해서 3을 만들때 => dp[0][2]

로 나타낼 수 있다.

이는 dp[n][k] = k번 더해서 합이 n이되는 경우의 수 이기때문이다.

위를 바탕으로 N = 5, K = 3 일때의 dp를 구하면 다음과 같다.

따라서 0부터5까지 정수를 3번 더해서 합이 5가되는 경우의 수는 21이 된다.dp[5][3]

이를 코드로 구현하면 다음과 같다.

import Foundation

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

// DP 입력
// dp[n][k] = dp[n][k] + dp[i][k-1] (i는 0부터 n까지의 정수)
for i in 1...input[1] {
    for j in 0...input[0] {
        if i == 1 || j == 0 {
            dp[j][i] = 1
            continue
        }
        for k in 0...j {
            dp[j][i] = (dp[j][i] + dp[k][i-1]) % 1000000000
        }
    }
}
print(dp[input[0]][input[1]])

내가 푼 풀이

- BFS로 인접한 접점을 탐색해서 걸린 시간을 출력한다.

- 예제로 주어진 X = 5, K = 17 일때 다음과 같다.

- 이미 방문했던 지점이라면 스킵하고, 방문하지 않은 지점이라면 걸린시간을 더해준다.

- 걸린시간을 계산하기위해 dp[] 의 크기를 100,000만큼 선언해준다. ( 이 문제의 최대지점이 100,000 이기때문에)

- BFS 방식으로 인접한 지점 우선으로 탐색하고, 방문하지 않은 지점이라면 dp[방문할지점] = dp[이전 지점] + 1 을 해준다.

- 위에선 지점 5에서 4로갈때 1초가 들고, 지점 4에서 3으로 갈때, dp[3] = dp[4] + 1 이 된다.

- 이미 방문한 지점을 배열로 선언하여 contains 함수를 이용해 방문 했는지 확인하려 했으나, 시간초과가 떴다.

- BFS, DFS 중 어떤방식을 써야하는지는 알지만, 해당 알고리즘을 코드로 구현할때, 시간초과가 걸리지않게 따로 저장하는 방식을 쓰자

import Foundation

var input = readLine()!.split(separator: " ").map{ Int($0)! }
var needVisitedQueue = [input[0]]
var idx = 0
var arr = [Int]()
var dp = Array(repeating: 0, count: 100001)
var visited = Array(repeating: 0, count: 100001)
visited[input[0]] = 1
// 소요시간을 저장할 배열 DP
// 해당 지점을 방문했는지 확인하기위한 배열 visited (visited[n] == 1 이면 지점 N은 이미 방문했다.)
// BFS로 시작점에서 인접한 노드순으로 탐색한다.
while idx < needVisitedQueue.count {
    var node = needVisitedQueue[idx]
    idx += 1
    if node == input[1] { break }
    
    // 해당 노드의 인접노드들이 범위안에 있고, 방문하지 않은곳이라면 다음방문 순서로 둔다.
    if node-1 >= 0 && visited[node-1] != 1 {
        needVisitedQueue.append(node-1)
        visited[node-1] = 1
        dp[node-1] = dp[node] + 1
    }
    if node+1 <= 100000 && visited[node+1] != 1 {
        needVisitedQueue.append(node+1)
        visited[node+1] = 1
        dp[node+1] = dp[node] + 1
    }
    if node*2 <= 100000 && visited[node*2] != 1 {
        needVisitedQueue.append(node*2)
        visited[node*2] = 1
        dp[node*2] = dp[node] + 1
    }
}

print(dp[input[1]])

문제

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

내가 푼 풀이

- 처음에는 토마토가 들어있지 않은 칸을 제외한 칸끼리의 연결리스트를 작성해, BFS를 실행 시켰는데 시간초과가 떴다.

- 위 같은 문제는 연결방향이 정해져있고, 범위도 정해져있기에 따로 연결리스트까진 필요없지만, 탐색을 시작할 점은 필요하다.

- 상자의 배열을 입력받아, 토마토가 들어있다면 탐색시작 인덱스로 저장해둔다.

- 시작 인덱스부터 상하좌우 방향으로 상자범위안에 있고, 익지않은 토마토가 있다면 해당토마토를 익힌다.

- 그리고 해당 칸의 경과일을 저장할 day 배열을 상자크기만큼 선언하고, 익지않은 토마토를 발견하면 인접한 익은 토마토의 day 원소 + 1 을 해준다.

- 마지막으로 토마토가 익은 위치를 저장해두고, 상자를 다시 확인했을때, 익지않은 토마토가 없다면, 마지막으로 익은 위치의 day 원소를 출력

- 익지 않은 토마토가 있다면, -1 출력

해당 조건대로 코드를 구현해 보자.

import Foundation

var input = readLine()!.split(separator: " ").map{ Int($0)! }
var arr = [[Int]]()
var days = Array(repeating: Array(repeating: 0, count: input[0]), count: input[1])
var needVisitQueue = [[Int]]()
var idx = 0
var endDay = [0,0]
var complete = true

// 상자 배열 입력
// 익은 토마토를 발견할 경우 해당 x,y 인덱스를 시작점 배열에 추가
for i in 0..<input[1] {
    arr.append(readLine()!.split(separator: " ").map{ Int($0)! })
    for j in 0..<arr[i].count {
        if arr[i][j] == 1 {
            needVisitQueue.append([j,i])
        }
    }
}
// 상하좌우 방향
var dx = [0, 1, 0, -1]
var dy = [1, 0, -1, 0]

// 탐색시작점부터 모든 인접한 위치 탐색
while idx < needVisitQueue.count {
    var node = needVisitQueue[idx]
    idx += 1
   
    for i in 0..<4 {
        let nx = node[0] + dx[i]
        let ny = node[1] + dy[i]

        if (nx >= 0 && nx < input[0]) && (ny >= 0 && ny < input[1]) {
            if arr[ny][nx] == 0 {
                arr[ny][nx] = 1
                needVisitQueue.append([nx,ny])
                days[ny][nx] = days[node[1]][node[0]] + 1
                endDay = [nx,ny]
            }
        }
    }
}

// 익지않은 토마토를 발견하면, 모두 익지 못하는 상황이다.
for i in 0..<arr.count {
    for j in 0..<arr[0].count {
        if arr[i][j] == 0 {
            complete = false
        }
    }
}

if complete {
    print(days[endDay[1]][endDay[0]])
} else {
    print(-1)
}

내가 푼 풀이

- 카드 합체는 서로다른 x y의 x번째 카드와 y번째 카드를 더한 후 해당카드들에 결과를 덮어 씌우는것이다.

- 카드 합체가 끝나고 모든 카드의 합을 구하는 것인데, 해당 값이 최솟값이 되어야한다.

- 이는 카드합체를 할때, 가장 작은 두 수끼리 합체하면 모든 카드의 합이 결국 최솟값이 된다.

- 주어진 카드를 오름차순으로 정렬 후, 0번째 원소와 1번째 원소를 합체하고, 결과를 다시 오름차순으로 정렬한다.

- 이를 반복해서 카드들의 합을 구하면 최솟값이 된다.

import Foundation

var input = readLine()!.split(separator: " ").map{ Int($0)! }
var arr = readLine()!.split(separator: " ").map{ Int($0)! }
arr.sort{$0 < $1}

// 카드 합체
// 카드는 오름차순으로 정렬되어있기에, 0번째 원소와 1번째 원소가 가장 작은 수 2개이다.
for i in 0..<input[1] {
    var sum = arr[0] + arr[1]
    arr[0] = sum
    arr[1] = sum
    arr = arr.sorted{ $0 < $1}
}

print(arr.reduce(0, +))

내가 푼 풀이

- 게이트에 최대로 도킹할 수 있는 비행기의 수를 구한다.

- P개의 줄에 숫자 N이 주어지면, 해당 비행기는 1부터 N까지의 게이트에 도킹할 수 있다.

- 이를 생각해보면 1은 1부터 1까지 1개, 5는 1부터 5까지 5개의 게이트 중 하나를 도킹할 수 있다는 의미다.

- 최대한 많은 비행기를 도킹시키려면 주어진 값의 최댓값부터 도킹을 해야 비행기를 최대로 도킹할 수 있다.

- 이를 위해 숫자 N이 주어지면 N부터 1까지 도킹되어 있지않으면 도킹하는 방법을 이용했지만 , 시간초과가 떴다.

- 이 문제는 Union-Find 알고리즘을 이용해서 풀어야한다.

Union-find를 이용하며 예제를 풀어본다.

게이트 수 G = 4, 비행기 수 P = 6, 도착하는 비행기 배열 [2, 2, 3, 3, 4, 4]

게이트를 배열로 표현한다.

처음에 각 게이트들은 자신의 게이트가 비어있으므로, 자신의 게이트를 가리킨다.

먼저 Gi가 2인 비행기가 도착하면, 해당 비행기는 1부터 2까지 최댓값인 곳에 도킹한다.

게이트 2가 현재 비어있으므로, 게이트 2에 도킹한다.

게이트 2에 도킹을 한다면, 게이트 2는 도킹할 수 없으므로 게이트 1을 가리킨다.

이는 Union-find에서 find(2)-1 , find(2)를 union 하는 것이다.

다음에 Gi가 2인 비행기가 도착한다.

2번 게이트에 도킹하려 했지만, 이미 2번게이트에 도킹이 되어있다.

2번 게이트는 1번을 가리키므로, 1번 게이트에 도킹을 한다.

이때 find(1) - 1과 find(1)을 union 한다. (0, 1)

위 배열로 보았을 때, Gi가 2나 1인 비행기가 오면 더 이상 도킹할 수 없는 상황이다.

다음 비행기의 Gi는 3이다.

3번 게이트에 도킹을 하고, 2번과 union을 해준다.

그다음 비행기의 Gi값이 3이지만, 3번 게이트부터 1번 게이트까지 모두 자리가 없으므로, 종료한다.

이 문제는 이해하기 쉽지만, 결국 Union-find 알고리즘을 알고 있는지 물어보는 문제인듯하다..

위 알고리즘을 통해 코드로 구현해 보자.

import Foundation

var g = Int(readLine()!)!
var p = Int(readLine()!)!
var arr = Array(1...g)
arr.insert(0, at: 0)
var result = 0

// Union-find 의 find
func find(_ x: Int) -> Int {
    if arr[x] == x { return x}
    arr[x] = find(arr[x])
    return arr[x]
}
// Union-find 의 union
func union(x: Int, y: Int) {
    arr[find(y)] = find(x)
}

for i in 0..<p {
    var num = Int(readLine()!)!
    // 해당 비행기가 도킹할 수 있는지?
    // 도킹했다면 union을 통해 배열 최신화
    if find(num) == 0 { break }
    result += 1
    union(x: find(num) - 1, y: find(num))
}
print(result)

내가 푼 풀이

- k원이 되도록 n가지 동전의 개수가 최소가 되게끔 한다.

- 기본적으로 k원이 될때, n가지 동전 중 가치가 높은 동전을 최대한 많이 사용하면 개수가 최소가 된다.

- dp [n] = n원이 되도록 하는 동전의 최소개수 라 정의하자.

- 예제 입력을 통해 어떻게 코드로 구현했는지 보자.

n = 3, k = 15, [1,5,12] : 3가지의 동전으로 15원을 만드는 동전의 최소개수는?

위의  입력이 주어졌을 때, 동전을 한번 사용하는 경우 : dp[1] = 1 , dp[5] = 1, dp[12] = 1 이 된다.

- 2원: 1원 + 1원  -> dp[2] = dp[1] + 1

- 3원: 2원 + 1원  -> dp[3] = dp[2] + 1

- 4원: 3원 + 1원  -> dp[4] = dp[3] + 1

- 5원: 4원 + 1원,  5원 dp[5] = min(dp[0] + 1 , dp[4] + 1)

5원을 만들 수 있는 경우의 수 중 최솟값을 저장한다. 

dp[n] 은 n원을 만드는 최소 동전개수이므로 1원 6개를 만드는 경우는 배제하고, 6원을 만드는 최적의 방법만 검사한다.

- 6원: 5원 + 1원 : dp[6] = dp[5] + 1

- 10원: 5원 2개,  9원 + 1원 : min( dp[5] + 1 , dp[9] + 1 )

위와 같이 n원을 만들 때, 사용 가능한 동전들의 경우의 수들 중 최솟값을 저장한다.

코드로 구현하면 다음과 같다.

import Foundation

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

// n가지 동전의 종류를 배열로 입력
for i in 0..<input[0] {
    var num = Int(readLine()!)!
    arr.append(num)
}

// DP 입력
// dp[n] = n원을 만드는 최소 동전 개수
for i in 1...input[1] {
    var a = [Int]()
    // 해당 동전을 사용할 수 있는지 확인한다.
    // 주어진 동전들을 이용해서 만들수 있는지 확인: dp[i-arr[j]] != -1
    for j in 0..<arr.count {
        if i - arr[j] >= 0 && dp[i-arr[j]] != -1 {
            a.append(dp[i-arr[j]] + 1)
        }
    }
    // 만들 수 없다면 -1
    // 만들 수 있다면 만드는 경우의 수 중 최솟값을 저장
    if a.isEmpty {
        dp[i] = -1
    } else {
        dp[i] = a.min()!
    }
}
print(dp[input[1]])

내가 푼 풀이

- 예제입력 1로 주어진 센서를 아래와 같이 표현하면 다음과 같다.

- 센서위치를 배열로 표현후 오름차순으로 정렬한다. [ 1, 3, 6, 6, 7, 9]

- 해당 입력으로 주어졌을때, 집중국의 수신가능 영역의 길이의 합 최솟값은 2 + 3 = 5이다.

- 정답을 도출하기 위해서, 각 센서사이의 거리를 구한다.

- 각 센서사이의 거리를 구한 후 오름차순으로 정렬하면 [0, 1, 2, 2, 3] 이 된다.

- 여기서 우리는 k개의 집중국을 설치하게 되는데,

- 집중국의 수신가능 영역의 길이의 합이 최소로 되게끔 k개의 집중국을 설치하면, 집중국과 집중국 사이의 빈 공간이 k-1개가 생긴다.

- 빈 공간 k-1개를 최대로 만들면 길이의 합이 최소로 된다.

- 센서사이의 거리 배열이 오름차순으로 정렬되어 있으니, k-1개만큼 마지막위치를 빼주고, 배열의 합을 구해주면 된다.

- 센서 위에 집중국을 설치하면, 그 집중국의 수신가능 영역이 0 이어도 같은 위치의 센서와 수신가능하다.

- 만약 센서의 개수와 집중국의 개수가 같다면, 센서 위에 집중국을 설치하면 모두 수신가능하므로 최솟값은 0이 된다.

위 방법으로 코드로 구현해 보자

import Foundation

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

// 배열을 입력받고, 오름차순으로 정렬
var arr = readLine()!.split(separator: " ").map{ Int($0)! }
arr.sort{ $0 < $1}

// 센서의 갯수가 1이거나 집중국의갯수와 같다면 최소합은 0이된다
// 센서사이의 거리를 구해 오름차순으로 정렬한 후 k-1개만큼 길이가 긴 범위를 빼준다.
if count == 1 || count == n {
    print(0)
} else {
    var sub = [Int]()
    for i in 0..<arr.count-1 {
        sub.append(arr[i+1] - arr[i])
    }
    sub.sort{ $0 < $1}
    for i in 0..<n-1 {
        sub.removeLast()
    }
    print(sub.reduce(0, +))
}

내가 푼 풀이

- 생각보다 많은 고민이 필요했던 문제다.

- 직접 그려보면서 확인한결과 N이 홀수일 때 주어진 크기의 타일로 절대 채울 수 없다.

- dp[n] = 3 x n 크기의 타일을 채우는 경우의 수라고 정해보자.

- dp[2] = 3

- dp[4] = dp[2] * 3 + 2 = 11

위 dp[2]를 이용한다면 dp[4] = dp[2] * 3 이 된다.

하지만 여기서 다른방식의 패턴이 나온다.

위와 같은 패턴이 크기가 4 이상인 타일에서 나온다.

위 두가지 패턴의 경우까지 합치면 dp[4] = dp[2] * 3 + 2 = 11이 된다.

- dp[6]

dp[6] 은 3 x 4 크기의 타일에서 2가 추가되었으므로

dp[4] * 3이 된다.

이는 4칸으로 가능한 모든 타일과 2칸이 추가되어서 2칸에서 만들 수 있는 타일의 경우의 수 3을 곱한 것이다.

또한 위 도형의 왼쪽 2칸을 채우는 경우의 수는 dp[2]이고 오른쪽의 4칸 타일의 경우의 수는 아래와 같다.

이 경우의 수는 dp[2] * 2로 나타낼 수 있다.

dp[6]에도 새로운 패턴의 타일이 있다.

위 세 가지 경우의 수를 합치면 dp[6] = dp[4] x 3 + dp[2] x 2 + 2가 된다.

위 경우의 수들을 종합하면 점화식은 다음과 같다.

dp[n] = dp[n-2] * 3 + (dp[n-4] * 2) + (dp[n-6] * 2) + .... + (dp[0] * 2) + 2 가된다.

코드로 구현해 보자.

import Foundation

var num = Int(readLine()!)!
var dp = Array(repeating: 0, count: 31)
// dp의 초기값 설정
// n이 홀수일때 주어진 타일로 채울 수 없다.
dp[0] = 0
dp[1] = 0
dp[2] = 3

// dp[n] = dp[n-2] * 3 + dp[n-4] * 2 + dp[n-6] * 2 + .... + dp[0] * 2 + 2
for i in stride(from: 4, through: 30, by: +2) {
    var sum = 0
    for j in stride(from: 0, through: i-4, by: +2) {
        sum += dp[j] * 2
    }
    dp[i] = dp[i-2] * 3 + 2 + sum
}

print(dp[num])