Jenikeju

내가 푼 풀이

- 예제입력 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])

문제

여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.

현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다.

  

지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오.

내가 푼 풀이

- dp테이블을 주어진 지도의 크기만큼 만든다.

- 한 지점을 선택했을때, 상하좌우보다 작은 값이라면, 이동할 수 있는 곳이다.

- 처음에는 위 조건대로 이중 반복문을 돌아 dp에 값을 입력하려고 했다.

- 반복문의 특성상 0행을 모두 돌고, 1행을 모두 돌고.... m행을 돌다 보니 위 예제그림 3번째처럼 왼쪽으로 이동하는 경우는 dp에 저장되지 않았다.

- 위 문제는 dfs + dp를 이용해 야했던 것이다.

- dfs로 0,0 지점에서 m, n지점으로 이동한 경우 해당 경로들의 dp값을 모두 1로 입력한다.

- 다른 갈래로 갔던 지점이 dp의 값이 1인경우 1 반환

import Foundation

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

// 지도를 배열로 입력
for i in 0..<input[0] {
    arr.append(readLine()!.split(separator: " ").map{ Int($0)! })
}

// DFS 재귀호출
// 상하좌우 방향이 현재위치보다 작은경우 이동가능한 곳이다.
// dp의 초기값은 -1이므로 새롭게 가는곳이다.
func dfs(_ x: Int, _ y: Int) -> Int {
    // 목적지에 도착하면 1반환
    if x == input[1] - 1 && y == input[0] - 1 {
        return 1
    }
    // 처음가보는곳이라면 해당위치의 상하좌우방향중 이동할 수 있는 곳으로 재귀호출
    if dp[y][x] == -1 {
        dp[y][x] = 0
        for i in 0..<4 {
            var ny = y + dy[i]
            var nx = x + dx[i]

            if (ny >= 0 && ny < input[0]) && (nx >= 0 && nx < input[1] ) {
                if arr[ny][nx] < arr[y][x] {
                    dp[y][x] += dfs(nx, ny)
                }
            }
        }
    }
    // 이미 이동했던곳이라면 저장된 DP값을 반환
    return dp[y][x]
}

print(dfs(0, 0))

내가 푼 풀이

- 주어진 땅을 배열로 입력받고, 인접한 인덱스의 연결리스트를 입력한다.

- 연결된 배추들을 탐색하고, 탐색이 완료된곳은 지렁이 한 마리가 필요하므로, 한 마리 카운트해 준다.

- 인접된 배추들을 탐색할 때, 순서가 중요하지 않으므로 BFS, DFS 둘 다 사용가능하다.

import Foundation

let count = Int(readLine()!)!

for i in 0..<count {
    var input = readLine()!.split(separator: " ").map{ Int($0)! }
    var arr = Array(repeating: Array(repeating: 0, count: input[0]), count: input[1])
    var graph = [[Int]: [[Int]]]()
    var result = 0
    
    // 주어진 땅을 배열로 입력
    for j in 0..<input[2] {
        var idx = readLine()!.split(separator: " ").map{ Int($0)! }
        arr[idx[1]][idx[0]] = 1
    }
    
    // 땅에 심어진 배추와 인접한 배추들의 위치를 연결리스트로 입력
    // [[x,y] : [[인접한 배추들의 위치들]]
    // 인접한 배추가 없는경우 자신의 위치 한곳에도 지렁이가 필요하므로 자신의 위치도 입력한다.
    for j in 0..<arr.count {
        for k in 0..<arr[0].count {
            if arr[j][k] == 0 { continue }
            if graph[[j,k]] == nil {
                graph[[j,k]] = [[j,k]]
            } else {
                graph[[j,k]]!.append([j,k])
            }
            if j > 0 && arr[j-1][k] == 1 {
                if !graph[[j,k]]!.contains([j-1, k]) {
                    graph[[j,k]]!.append([j-1,k])
                }
                if graph[[j-1,k]] == nil {
                    graph[[j-1,k]] = [[j,k]]
                } else {
                    if !graph[[j-1,k]]!.contains([j,k]) {
                        graph[[j-1,k]]!.append([j,k])
                    }
                }
            }
            if j < arr.count-1 && arr[j+1][k] == 1 {
                if !graph[[j,k]]!.contains([j+1, k]) {
                    graph[[j,k]]!.append([j+1,k])
                }
                if graph[[j+1,k]] == nil {
                    graph[[j+1,k]] = [[j,k]]
                } else {
                    if !graph[[j+1,k]]!.contains([j,k]) {
                        graph[[j+1,k]]!.append([j,k])
                    }
                }
            }
            if k > 0 && arr[j][k-1] == 1 {
                if !graph[[j,k]]!.contains([j, k-1]) {
                    graph[[j,k]]!.append([j,k-1])
                }
                if graph[[j,k-1]] == nil {
                    graph[[j,k-1]] = [[j,k]]
                } else {
                    if !graph[[j,k-1]]!.contains([j,k]) {
                        graph[[j,k-1]]!.append([j,k])
                    }
                }
            }
            if k < arr[0].count-1 && arr[j][k+1] == 1 {
                if !graph[[j,k]]!.contains([j, k+1]) {
                    graph[[j,k]]!.append([j,k+1])
                }
                if graph[[j,k+1]] == nil {
                    graph[[j,k+1]] = [[j,k]]
                } else {
                    if !graph[[j,k+1]]!.contains([j,k]) {
                        graph[[j,k+1]]!.append([j,k])
                    }
                }
            }
        }
    }
    
    // 인접한 배추들을 탐색하는데 순서가 중요하지 않으므로 BFS, DFS 둘다 사용가능하다.
    // 여기서는 BFS를 사용했다.
    var totalVisitedQueue = [[Int]]()
    var visitedQueue = [[Int]]()
    var needVisitQueue = [[Int]]()
    
    for j in 0..<arr.count {
        for k in 0..<arr[0].count {
            if arr[j][k] == 1 && !totalVisitedQueue.contains([j,k]) {
                needVisitQueue = [[j,k]]
                
                while !needVisitQueue.isEmpty {
                    var node = needVisitQueue.removeFirst()
                    if visitedQueue.contains(node) { continue }
                    visitedQueue.append(node)
                    
                    needVisitQueue += graph[node]!
                }
                totalVisitedQueue += visitedQueue
                result += 1
                visitedQueue.removeAll()
            }
        }
    }
    print(result)
    
}

내가 푼 풀이

- 주어진 보드판을 해당 폴리오미노로 바꾸면된다.

- 사전순으로 앞서는 답을 출력하기위해, A로 바꿀수있다면 최대한 A로 바꿔주면 된다.

import Foundation

var input = readLine()!
var arr = input.map{ String($0)}
var result = [String]()
var idx = 0

// 폴리오미노 덮기
// AAAA로 바꿀수 있다면 최대한 바꿔준다.
// 폴리오미노 둘다 길이가 2로 나눠지므로 만약 2로 나눠지지 않는다면 덮을 수 없다고 판단한다.
while idx < arr.count {
    if arr[idx] == "." {
        result.append(arr[idx])
        idx += 1
        continue
    }
    var count = 0
    while idx < arr.count && arr[idx] == "X" {
        count += 1
        idx += 1
    }
    while count > 0 {
        if count % 2 != 0 {
            result = ["-1"]
            break
        } else if count >= 4 {
            count -= 4
            result.append("AAAA")
        } else {
            count -= 2
            result.append("BB")
        }
    }
}
if result.contains("-1") {
    print("-1")
} else {
    print(result.joined(separator: ""))
}

내가 푼 풀이

- 이제까지 가장 긴 증가하는 부분수열에 대해 많이 풀어봤다.

- 같은 알고리즘에 등호만 다르다.

- dp[n] = a를 n번째원소까지의 감소하는 부분수열의 길이라 정의하자.

- 각 원소는 원소하나만으로 감소하는 부분수열의 길이 1을 갖는다.

- n번째 원소는 n-1번째 원소까지 값을 비교하며, n번째원소보다 작고, 중복되지 않는다면, dp[n]의 값을 증가시킨다.

예시로 주어진 [10,30,10,20,20,10] 수열에서

마지막원소 10을 검사할때, 이전의 원소들과 비교를 하게 된다.

20이 두 번 나와도, 첫 번째로 검사한 20에서 dp[n] 값을 증가시켰기 때문에

두 번째 20을 마주쳐도 dp[i] < dp[j] + 1 조건을 만족할 수 없기 때문에 중복되는 원소들을 배제시킬 수 있었다.

import Foundation

// 배열 입력받기
let count = Int(readLine()!)!
var arr = [0] + readLine()!.split(separator: " ").map{ Int($0)! }
var dp = Array(repeating: 1, count: count+1)
dp[0] = 0

// dp 입력
// i번째 원소보다 작은 j번째가 있는경우
// 해당하는 값이 이전에 나와있는지를 판단하기위해 dp[i] < dp[j] + 1 조건문을 걸었다.
for i in 1...count {
    for j in 1..<i {
        if arr[i] < arr[j] && dp[i] < dp[j] + 1 {
            dp[i] += 1
        }
    }
}
print(dp.max()!)

문제

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

내가 푼 풀이

- 집이 있는곳을 기준으로 상하좌우에 중에 1이 있는 곳은 인접한 집이 있다는 것이고, 단지를 이룬다.

- 집이있지만 주변에 인접한 집이 없는 경우에도, 그 집 한 채는 단지를 이룬다고 본다.

- 주어진 N크기의 정사각형지도를 배열로 만들고, 인접한집의 리스트를 만든다.

- 여기서 주변에 인접한 집이 없어도, 자기집 하나로 단지를 이루기에 자신의 인덱스까지 리스트에 넣는다.

- graph[[Int]: [[Int]]] ----> [x, y]: [인접한 집의 x, y들]

- 위 문제에서는 집과 집사이의 순서는 필요 없기 때문에, BFS DFS 어떤 것이든 사용하든 상관없다.

- 그래프탐색을 이용해 인접한 집들을 모두 탐색하면, 단지의 집의 개수가 나온다.

- 나온 단지들의 개수와 단지 안에 있는 집의 개수를 오름차순으로 정렬 후 출력한다.

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

import Foundation

let size = Int(readLine()!)!
var arr = [[Int]]()
var graph = [[Int]: [[Int]]]()
var result = [Int]()

// 주어진 지도를 배열로 입력
for i in 0..<size {
    arr.append(readLine()!.map{Int(String($0))!})
}

// 배열을 통해 집과 인접한 집들의 위치를 저장한다.
// 주변에 인접한 집이 없어도, 자신의 집 한채로 단지를 이룬다고 보기에 자신의 위치 x,y도 리스트에 저장한다.
for i in 0..<size {
    for j in 0..<size {
        if arr[i][j] == 1 {
            if graph[[i,j]] == nil {
                graph[[i,j]] = [[i,j]]
            } else {
                graph[[i,j]]!.append([i,j])
            }
            if i > 0 && arr[i-1][j] == 1 {
                if graph[[i,j]] == nil {
                    graph[[i,j]] = [[i-1, j]]
                } else if !graph[[i,j]]!.contains([i-1,j]) {
                    graph[[i,j]]!.append([i-1,j])
                }
                if graph[[i-1,j]] == nil {
                    graph[[i-1,j]] = [[i, j]]
                } else if !graph[[i-1,j]]!.contains([i,j]) {
                    graph[[i-1,j]]!.append([i,j])
                }
            }
            if j < size-1 && arr[i][j+1] == 1 {
                if graph[[i,j]] == nil {
                    graph[[i,j]] = [[i, j+1]]
                } else if !graph[[i,j]]!.contains([i,j+1]) {
                    graph[[i,j]]!.append([i,j+1])
                }
                if graph[[i,j+1]] == nil {
                    graph[[i,j+1]] = [[i, j]]
                } else if !graph[[i,j+1]]!.contains([i,j]) {
                    graph[[i,j+1]]!.append([i,j])
                }
            }
            if i < size-1 && arr[i+1][j] == 1 {
                if graph[[i,j]] == nil {
                    graph[[i,j]] = [[i+1, j]]
                } else if !graph[[i,j]]!.contains([i+1,j]) {
                    graph[[i,j]]!.append([i+1,j])
                }
                if graph[[i+1,j]] == nil {
                    graph[[i+1,j]] = [[i, j]]
                } else if !graph[[i+1,j]]!.contains([i,j]) {
                    graph[[i+1,j]]!.append([i,j])
                }
            }
            if j > 0 && arr[i][j-1] == 1 {
                if graph[[i,j]] == nil {
                    graph[[i,j]] = [[i, j-1]]
                } else if !graph[[i,j]]!.contains([i,j-1]) {
                    graph[[i,j]]!.append([i,j-1])
                }
                if graph[[i,j-1]] == nil {
                    graph[[i,j-1]] = [[i, j]]
                } else if !graph[[i,j-1]]!.contains([i,j]) {
                    graph[[i,j-1]]!.append([i,j])
                }
            }
        }
    }
}


var totalVisited = [[Int]]()
var visitedQueue = [[Int]]()
var needVisitedQueue = [[Int]]()

// 그래프 탐색의 순서가 의미없기에, 배열을 순회하며 집을 발견하면 단지 탐색을 한다.
// BFS를 사용했다. (DFS를 사용해도 무관)
// 단지을 탐색후 발견한 집의 개수를 따로 저장하고, 발견한 집들의 위치는 다시 탐색할 필요가 없다.
for i in 0..<size {
    for j in 0..<size {
        if arr[i][j] == 1 && !totalVisited.contains([i,j]) {
            needVisitedQueue = [[i,j]]

            while !needVisitedQueue.isEmpty {
                var node = needVisitedQueue.removeFirst()
                if visitedQueue.contains(node) { continue }
                visitedQueue.append(node)

                needVisitedQueue += graph[node]!
            }
            totalVisited += visitedQueue
            result.append(visitedQueue.count)
            visitedQueue.removeAll()
        }
    }
}
result.sort{ $0 < $1 }
print(result.count)
for i in result {
    print(i)
}

내가 푼 풀이

- 체스판에서 나이트가 움직인다면, 위 아래는 자유자재로 움직이지만, 반드시 오른쪽으로 이동이 된다.

- 체스판에서 나이트의 움직임은 최대한 오른쪽으로 적게 가야 많이 움직이게 된다.

- 이는 나이트가 방문하는 칸의 최대가 되려면, 오른쪽으로 최대한 적게 움직여야 한다.

- 나이트의 최적의 움직임은 1번 4번을 반복해서 오른쪽으로 최대한 적게 움직이는 것이다.

- 나이트의 이동 횟수가 4번보다 적지 않다면 위 4가지 모두 한 번씩은 사용해야 한다.

- 이는 체스판의 크기 기준으로 4번 모두 움직일 수 있는 크기의 체스판이 주어진다면, 1번, 2번, 3번, 4번 움직임 모두 소화해 낸다.

- 반대로 크기가 작다면 최고효율의 움직임만 실행한다.

- 1번, 2번, 3번, 4번 모두 이동가능한 체스판의 크기는 어느 정도 일까

- 세로이동은 +2 , +1 , -1 , -2이다. 세로의 크기는 3칸 정도 되면 모두 움직일 수 있다.

- 가로이동은 +1 , +2 , +2 , +1이다. 가로의 크기는 7칸 정도 되면 모두 움직일 수 있다.

- 이는 나이트의 시작지점이 주어져있기 때문에, 3X7 크기 이상의 체스판이 주어진다면, 가능한 모든 움직임을 한 번씩 소화시킨다.

위와 같이 모든 움직임을 한번씩 소화했을 때의 경우이다.

- 세로의 크기가 3보다 작다면

세로의 크기가 1이면 움직일 수 없다.

세로의 크기가 2라면

위와 같이 2번, 3번 이동만 가능하지만, 이동방법을 모두 사용하지 않았으므로 방문가능한 지점은 가로가 아무리 길어도 최대 4가 된다.

- 가로의 크기가 7보다 작다면

위와 같이 1번, 4번 이동으로 최대한 많은 지점을 방문했지만, 이동방법을 모두 사용하지 않았으므로 방문가능한 지점은 최대 4가 된다.

위의 경우바탕으로 코드로 구현해 보자.

import Foundation

var input = readLine()!.split(separator: " ").map{ Int($0)! }
var result = 1
var num = 0
var idx = 1

// 세로의 길이를 기준으로 길이가 1이면 이동 불가능
// 길이가 2이면 2,3번 이동방법 가능
if input[0] == 2 {
    result = (input[1] + 1) / 2
    if result > 4 {
        result = 4
    }
} else if input[0] > 2 {
    // 가로의길이가 7보다 크다면, 모든 이동방법 이용가능
    // 모든 이동방법을 한번씩 사용한 후, 남은 크기를 가장 효율적인 이동인 1번,4번으로만 이동
    if input[1] > 6 {
        result = 5
        idx = 7
        num = input[1] - 7
        result = result + num
    } else {
        // 가로의 길이가 7보다 작아도, 가장 효율적인 이동인 1번,4번을 이용하지만
        // 모든 이동방법을 사용하지 않았으므로 방문지점은 최대4가된다.
        result = result + input[1] - 1
        if result > 4 {
            result = 4
        }
    }
}

print(result)