Jenikeju

내가 푼 풀이

- 주어진 N * N 게임판과 같은 크기의 배열 dp를 선언한다.

- (0, 0) 에서 반드시 오른쪽, 아래로만 이동가능하고, 도착점은 (n-1, n-1) 지점이다.

- 이중 반복문은 1행 1열,2열,3열, ... , 2행 1열,2열3열, .... , n행 1열 순으로 순회하므로 이동은 항상 인덱스에서 더해지기 때문에

- 이동한 지점에 이전 dp값을 더하는 방식으로 풀었다.

- dp[i][j] = i행j열까지의 이동한 경로의 수

import Foundation

let n = Int(readLine()!)!
var arr = [[Int]]()
var dp = Array(repeating: Array(repeating: 0, count: n), count: n)

// 게임판 입력
for i in 0..<n {
    arr.append(readLine()!.split(separator: " ").map{ Int($0)! })
}
dp[0][0] = 1

// DP
// 이동한지점은 이전지점의 DP값을 더해가는 방식을 사용
for i in 0..<n {
    for j in 0..<n {
        if dp[i][j] != 0 && arr[i][j] != 0 {
            let m = arr[i][j]
            if i+m < n {
                dp[i+m][j] += dp[i][j]
            }
            if j+m < n {
                dp[i][j+m] += dp[i][j]
            }
        }
    }
}

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

문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

내가 푼 풀이

- 주어진 체스판에서 시작점부터 BFS 탐색으로 이동한 곳에 +1 카운트를 해준다.

- 따로 카운트해줄 배열 dp를 선언해 저장하고, 도착점이 목적지랑 같은경우 탐색 종료해준다.

import Foundation

let c = Int(readLine()!)!

// 나이트의 이동
var dx = [1, 2, -1, -2, 1, 2, -1, -2]
var dy = [2, 1, -2, -1, -2, -1, 2, 1]

for i in 0..<c {
    var len = Int(readLine()!)!
    var board = Array(repeating: Array(repeating: 0, count: len), count: len)
    var dp = Array(repeating: Array(repeating: 0, count: len), count: len)
    var s = readLine()!.split(separator: " ").map{ Int($0)! }
    var d = readLine()!.split(separator: " ").map{ Int($0)! }
    
    var needVisitQueue = [(x: s[0], y: s[1])]
    
    // BFS
    // 나이트를 움직일때 도착점이 탐색하지 않은곳이라면 +1 카운트
    // 이미 도착했던곳이라면 스킵한다.
    while !needVisitQueue.isEmpty {
        var loc = needVisitQueue.removeFirst()
        if loc.x == d[0] && loc.y == d[1] { break }
        
        for i in 0..<8 {
            var mx = loc.x + dx[i]
            var my = loc.y + dy[i]
            
            if (mx >= 0 && mx < len) && (my >= 0 && my < len) && (dp[mx][my] == 0){
                dp[mx][my] = dp[loc.x][loc.y] + 1
                needVisitQueue.append((x: mx, y: my))
            }
        }
    }
    print(dp[d[0]][d[1]])
}

    +---+        
    | D |        
+---+---+---+---+
| E | A | B | F |
+---+---+---+---+
    | C |        
    +---+        

내가 푼 풀이

- 주어진 n^3개의 주사위를 적당히 회전시켜서 쌓아 올린 n * n * n크기의 정육면체를 만들때의 보이는 5개면의 합 최솟값을 구한다.

- 바닥과 마주본 면은 보이지 않으므로 합에서 제외된 5개의 면이다.

- 주사위를 쌓아올렸을때, 보이는 면의개수의 경우의 수는 3가지이다.

- 주사위의 3개의 면이 보이는경우, 2개의 면이 보이는 경우, 1개의 면이 보이는 경우 이다.

- 해당 3가지 경우의수 모두 최솟값으로 구한다면, 쌓아 올린 정육면체의 5개면의 합이 최솟값이 된다.

- 처음에는 노가다로 주사위의 면 하나를 기준으로 했을 때, 3개의 면이 보이는 경우의 수를 모두 구하고, 중복되는 값을 소거했다.

- 2개의 면을 구할때도 모든 경우의 수를 구하고 중복된 경우의 수를 제거하여서 구한 값 중 최솟값을 구했다.

- 3가지 경우의 수를 구했다면 n * n * n 의 정육면체에서 이전에 경우의 수가 몇 개나 구성되어 있는지 파악한다.

• 3개의 면이 보이는 주사위 개수 : 4개
• 2개의 면이 보이는 주사위 개수 : 4 * (N-1) + 4 *(N-2)
• 1개의 면이 보이는 주사위 개수: 4 * (N-1) * (N-2) + 4 * (N-2)^2

모든 경우의수를 노가다로 구했을 때의 코드는 다음과 같다.

let n = Int(readLine()!)!
var arr = readLine()!.split(separator: " ").map{ Int($0)! }
var num3 = [Int]()
var num2 = [Int]()

// ABC ABD ACE ADE
// BDF BCF CEF DEF
num3 = [arr[0] + arr[1] + arr[2],
        arr[0] + arr[1] + arr[3],
        arr[0] + arr[2] + arr[4],
        arr[0] + arr[3] + arr[4],
        arr[1] + arr[3] + arr[5],
        arr[1] + arr[2] + arr[5],
        arr[2] + arr[4] + arr[5],
        arr[3] + arr[4] + arr[5]
        ]

// AB AC AD AE
// BC BD BF CF
// CE DE DF EF
num2 = [arr[0] + arr[1],
        arr[0] + arr[2],
        arr[0] + arr[3],
        arr[0] + arr[4],
        arr[1] + arr[2],
        arr[1] + arr[3],
        arr[1] + arr[5],
        arr[2] + arr[5],
        arr[2] + arr[4],
        arr[3] + arr[4],
        arr[3] + arr[5],
        arr[4] + arr[5]
        ]

var num3Min = num3.min()!
var num2Min = num2.min()!
var num1Min = arr.min()!

if n == 1 {
    print(arr.reduce(0, +) - arr.max()!)
} else {
    print(num3Min * 4 + num2Min * ((n-1) * 4 + (n-2) * 4) + num1Min * (4 * (n-1) * (n-2) + (n-2) * (n-2)))
}

해당 코드는 정답이 떴지만 주사위의 원리를 좀 이용해보려 한다.

A와 마주 보는 면은 F

B와 마주보는면은 E

C와 마주보는면은 D이다.

3면이 보이는 주사위를 회전시켜서 보일 때, 각 보이는 면과 마주 보는 면은 같이 보일 수 없다.

따라서 3면이 보이는 숫자를 최소로 만들려면 위의 세 가지를 모두 더한 값을 최솟값으로 만들면 된다.

2면이 보이는 주사위도 마찬가지로 위에 세 가지 중 작은 두 가지를 더한 값이 최솟값이 된다.

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

import Foundation

let n = Int(readLine()!)!
var arr = readLine()!.split(separator: " ").map{ Int($0)! }

var min1 = min(arr[0], arr[5])
var min2 = min(arr[1], arr[4])
var min3 = min(arr[2], arr[3])

var sortedArr = [min1, min2, min3].sorted{ $0 < $1}
var num1Min = sortedArr[0]
var num2Min = sortedArr[0] + sortedArr[1]
var num3Min = sortedArr[0] + sortedArr[1] + sortedArr[2]


if n == 1 {
    print(arr.reduce(0, +) - arr.max()!)
} else {
    var result = 0
    result += num3Min * 4
    result += (num2Min * (n-1) * 4 + num2Min * (n-2) * 4)
    result += (num1Min * (n-1) * (n-2) * 4 + num1Min * (n-2) * (n-2))
    print(result)
}

문제

N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다.

먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다.

별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가 다음 줄로 내려갈 수 있는 위치이며, 빨간 가위표는 원룡이가 내려갈 수 없는 위치가 된다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성하시오. 점수는 원룡이가 위치한 곳의 수의 합이다.

내가 푼 풀이

- 문제 내려가기 게임의 원리 자체도 쉬워서 구현도 쉬웠다.

- 내려가기의 원리를 반대로 생각하면

첫 번째 원소는 이전의 첫 번째와 두 번째 원소로부터

두 번째 원소는 이전에 모든 원소로부터

세 번째 원소는 이전에 두 번째와 세 번째 원소로부터 더해지는 것이다.

- 3 크기의 dp배열을 선언해서 이전의 값을 저장하고 이후에 나오는 원소들과 더해서 최댓값, 최솟값을 저장해서 출력한다.

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

import Foundation

let count = Int(readLine()!)!
var maxDp = Array(repeating: 0, count: 3)
var minDp = Array(repeating: 0, count: 3)

// DP 입력
// 이전의 값과 새로 추가되는 원소와 더해서 최대값 최소값을 넣는다.
for i in 0..<count {
    let arr = readLine()!.split(separator: " ").map{ Int($0)! }
    if i == 0 {
        maxDp = arr
        minDp = arr
        continue
    }
    let dp1 = maxDp
    let dp2 = minDp
    maxDp[0] = max(arr[0] + dp1[0], arr[0] + dp1[1])
    maxDp[1] = max(arr[1] + dp1[0], arr[1] + dp1[1], arr[1] + dp1[2])
    maxDp[2] = max(arr[2] + dp1[1], arr[2] + dp1[2])
    
    minDp[0] = min(arr[0] + dp2[0], arr[0] + dp2[1])
    minDp[1] = min(arr[1] + dp2[0], arr[1] + dp2[1], arr[1] + dp2[2])
    minDp[2] = min(arr[2] + dp2[1], arr[2] + dp2[2])

}

print("\(maxDp.max()!) \(minDp.min()!)")

내가 푼 풀이

- 주어진 연결된 두 정점을 연결리스트로 저장한다.

- 트리의 루트는 1 이므로 1부터 인접한 곳을 탐색한다.

- 이때 인접한 곳의 부모노드는 이전에 탐색된 노드의 번호가 되는 것이다.

- 인접한 노드 중 이미 탐색한 곳을 제외하고 새롭게 인접한 곳을 탐색한다.

- 부모노드를 배열에 따로 저장하고 출력

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

import Foundation

// 부모노드배열, 트리 연결리스트
let count = Int(readLine()!)!
var tree = [Int: [Int]]()
var parent = Array(repeating: 0, count: count+1)

// 연결리스트 입력
for i in 0..<count-1 {
    let input = readLine()!.split(separator: " ").map{ Int($0)! }
    if tree[input[0]] == nil {
        tree[input[0]] = [input[1]]
    } else {
        tree[input[0]]!.append(input[1])
    }
    if tree[input[1]] == nil {
        tree[input[1]] = [input[0]]
    } else {
        tree[input[1]]!.append(input[0])
    }
}

// 시작점은 루트노드 1
var needVisitQueue = [1]

// BFS
// 인접한 노드 탐색
// 이미 탐색한 곳은 제외하고 새롭게 탐색한다.
// 인접한 노드의 부모노드는 이전에 탐색된 노드번호가 된다.
while !needVisitQueue.isEmpty {
    var node = needVisitQueue.removeLast()
    var arr = [Int]()
    for i in tree[node]! {
        if parent[i] == 0 && i != node {
            parent[i] = node
            arr.append(i)
        }
    }
    needVisitQueue += arr
}

// 부모노드 출력
for i in 2...count {
    print(parent[i])
}

문제

남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 차가 최소가 되게 하려 한다.

통나무 건너뛰기의 난이도는 인접한 두 통나무 간의 높이의 차의 최댓값으로 결정된다. 높이가 {2, 4, 5, 7, 9}인 통나무들을 세우려 한다고 가정하자. 이를 [2, 9, 7, 4, 5]의 순서로 세웠다면, 가장 첫 통나무와 가장 마지막 통나무 역시 인접해 있다. 즉, 높이가 2인 것과 높이가 5인 것도 서로 인접해 있다. 배열 [2, 9, 7, 4, 5]의 난이도는 |2-9| = 7이다. 우리는 더 나은 배열 [2, 5, 9, 7, 4]를 만들 수 있으며 이 배열의 난이도는 |5-9| = 4이다. 이 배열보다 난이도가 낮은 배열은 만들 수 없으므로 이 배열이 남규가 찾는 답이 된다.

원소 7)

원소 5)

원소 4)

원소 2)

이렇게 정렬된 배열은 인접한 통나무의 높이 차가 최소가 된 배열이 된다.

해당 통나무 건너뛰기 난이도는 인접한 차이중 최대가 되는 9-5 = 4 가된다.

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

import Foundation

// 테스트케이스 수
let c = Int(readLine()!)!

for i in 0..<c {
    // 주어진 통나무 수 와 높이 배열 입력
    let count = Int(readLine()!)!
    var arr = readLine()!.split(separator: " ").map{ Int($0)! }
    
    // 오름차순
    var sortedArr = arr.sorted{$0 < $1}
    
    // 배열 정렬
    var max = sortedArr.removeLast()
    var arr1 = [Int]()
    var arr2 = Array(repeating: 0, count: sortedArr.count / 2)
    var idx = 0
    while idx < sortedArr.count {
        if idx+1 == sortedArr.count {
            arr1.append(sortedArr[idx])
            idx += 1
        } else {
            arr1.append(sortedArr[idx])
            arr2[arr2.count-1-(idx/2)] = sortedArr[idx+1]
            idx += 2
        }
    }
    arr1.append(max)
    var r = arr1 + arr2
    
    // 인접한 통나무의 높이차이를 비교하여 가장 큰 차이를 저장
    var min = -1
    for j in 0..<r.count {
        var num = Int()
        if j == r.count - 1 {
            num = r[j] - r[0]
        } else {
            num = r[j] - r[j+1]
        }
        if min < abs(num) { min = abs(num) }
    }
    print(min)
}

문제

유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다.

오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다.

파이프는 회전시킬 수 있으며, 아래와 같이 3가지 방향이 가능하다.

파이프는 매우 무겁기 때문에, 유현이는 파이프를 밀어서 이동시키려고 한다. 벽에는 새로운 벽지를 발랐기 때문에, 파이프가 벽을 긁으면 안 된다. 즉, 파이프는 항상 빈 칸만 차지해야 한다.

파이프를 밀 수 있는 방향은 총 3가지가 있으며, →, ↘, ↓ 방향이다. 파이프는 밀면서 회전시킬 수 있다. 회전은 45도만 회전시킬 수 있으며, 미는 방향은 오른쪽, 아래, 또는 오른쪽 아래 대각선 방향이어야 한다.

파이프가 가로로 놓여진 경우에 가능한 이동 방법은 총 2가지, 세로로 놓여진 경우에는 2가지, 대각선 방향으로 놓여진 경우에는 3가지가 있다.

아래 그림은 파이프가 놓여진 방향에 따라서 이동할 수 있는 방법을 모두 나타낸 것이고, 꼭 빈 칸이어야 하는 곳은 색으로 표시되어져 있다.

가로

세로

대각선

가장 처음에 파이프는 (1, 1)와 (1, 2)를 차지하고 있고, 방향은 가로이다. 파이프의 한쪽 끝을 (N, N)로 이동시키는 방법의 개수를 구해보자.

- 해당 문제를 봤을때 dfs로 풀 수 있을 정도의 크기지만, dp로 풀어보도록 했다.

- dp로 푸는경우에는 세가지의 경우를 생각해야했다.

- 가로로 가는방향, 세로로 가는방향, 대각선으로 가는방향 세가지를 3차원배열로 저장한다.

- dp[n][n] = (n,n) 까지 가는 경우의 수 라고 한다면, 2차원 배열로 입력했을때, 가로로 뻗어있을때 세로로 갈 수 없는 경우의 수까지 세게된다.

- dp[가로][n][n] , dp[세로][n][n], dp[대각선][n][n]으로 정의하여 현재 위치에서 가로 세로 대각선으로 갈 수 있다면 해당 배열의 위치에 dp값을 저장하고 세가지방법을 모두 더한다.

- 맨 처음 파이프는 (0,0) 에서 (0,1)로 가로로 뻗어있다.

- 파이프를 놓는 원리는 단순했지만, 원리안에 있는 조건을 dp입력할때 이용하는게 어려웠다.

import Foundation

let n = Int(readLine()!)!
var arr = [[Int]]()
var dp = [[[Int]]]()

for i in 0..<n {
    arr.append(readLine()!.split(separator: " ").map{ Int($0)! })
}

// 3차원 dp 선언
// 가로: 0, 세로: 1, 대각선: 2
for i in 0..<3 {
    var a = [[Int]]()
    dp.append(Array(repeating: Array(repeating: 0, count: n), count: n))
}

// 처음 파이프는 (0,0) 에서 (0,1)로 놓여져있다.
dp[0][0][1] = 1

// 파이프를 놓을 수 있는 조건에 맞게 dp값 입력
for i in 0..<n {
    for j in 0..<n {
        if i == 0 && j == 0 { continue }

        if j+1 < n && arr[i][j+1] == 0 {
            dp[0][i][j+1] += dp[0][i][j]
            dp[0][i][j+1] += dp[2][i][j]
        }
        if i+1 < n && arr[i+1][j] == 0 {
            dp[1][i+1][j] += dp[1][i][j]
            dp[1][i+1][j] += dp[2][i][j]
        }
        if i+1 < n && j+1 < n && arr[i+1][j] == 0 && arr[i][j+1] == 0 && arr[i+1][j+1] == 0 {
            dp[2][i+1][j+1] += dp[0][i][j]
            dp[2][i+1][j+1] += dp[1][i][j]
            dp[2][i+1][j+1] += dp[2][i][j]
        }
    }
}

print(dp[0][n-1][n-1] + dp[1][n-1][n-1] + dp[2][n-1][n-1])

내가 푼 풀이

- 비가 아예오지않는 경우 높이가 0 일 때부터 비가 최대치로 오는 경우 높이가 배열의 자연수중 가장 높은 수 까지 조사한다.

- 조사할때 인접한 경우는 배열의 상하좌우가 붙어있다면 인접한 경우로 본다.

- BFS로 비가 오는 높이보다 높은 안전지역을 모두 탐색한다면 안전영역의 개수를 카운트해준다.

- 카운트한 개수는 최댓값을 항상 갱신해 준다.

import Foundation

let n = Int(readLine()!)!
var arr = [[Int]]()
var max = 0
var result = 0
// 상하좌우 방향
var dx = [1,0,-1,0]
var dy = [0,1,0,-1]

// 주어진 N * N 배열 입력
// 높이의 최대값 저장
for i in 0..<n {
    arr.append(readLine()!.split(separator: " ").map{ Int($0)! })
    if max < arr[i].max()! {
        max = arr[i].max()!
    }
}

// BFS
// 비가 아예오지않는 0 부터 최대높이 max까지 오는 모든 경우의 수 조사
// 비의 높이보다 큰 안전한영역의 개수 카운트하고, 최대값 갱신
for i in 0...max {
    var needVisitQueue = [(x:Int, y: Int)]()
    var copy = arr
    var count = 0
    for j in 0..<n {
        for k in 0..<n {
            if copy[j][k] > i {
                needVisitQueue = [(x: k, y: j)]
                copy[j][k] = -1
                while !needVisitQueue.isEmpty {
                    var loc = needVisitQueue.removeLast()
                    
                    for m in 0..<4 {
                        var x1 = loc.x + dx[m]
                        var y1 = loc.y + dy[m]
                        
                        if (x1 >= 0 && x1 < n) && (y1 >= 0 && y1 < n) {
                            if copy[y1][x1] > i {
                                copy[y1][x1] = -1
                                needVisitQueue.append((x: x1, y: y1))
                            }
                        }
                    }
                }
                count += 1
            }
        }
    }
    
    if count > result {
        result = count
    }
}
print(result)