Jenikeju

내가 푼 풀이

- 연산의 최대횟수가 100,000이고, 배열의 크기가 최대 1024이므로 단순히 주어진 연산의 범위만큼 반복문을 돌리면,

최악의 경우 연산횟수가 100,000 * 1024 * 1024나 되므로, 계산된값을 저장하고 이용하기로 했다.

- 주어진 (N+1) x (N+1) 크기의 배열 dp를 선언한다.

- 행과 열이 인덱스가 0인경우 0을 넣어준다.

- dp[i][j] = 1행 1열부터 i행 j열까지 더한 범위의 값이라고 정의하자.

- (x1, y1) , (x2, y2) 가 주어졌을때,

- 예시로 4 x 4 배열이 주어졌을때, (2, 2) (3,4)의 범위는 아래와같다.

이 범위의 연산결과는 아래처럼 나타낼 수 있다.

위의 큰 배열에서 

위 두가지 범위를 빼준 후

이 범위를 더해주면 된다.

이를  0,0부터 i,j까지의 연산범위합이 들어간 dp[i][j]를 이용하면 아래와 같이 나타낼 수 있다.

- dp[3][4] - dp[1][4] - dp[4][1] + dp[1][1] 

위 공식을 이용해서 연산결과들을 출력한다.

(x1, y1) , (x2, y2) 의 범위가 주어졌을때, 해당 범위의 연산결과는

dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1] 

import Foundation

var counts = readLine()!.split(separator: " ").map{ Int($0)! }
var arr = [Array(repeating: 0, count: counts[0] + 1)]
var dp = Array(repeating: Array(repeating: 0, count: counts[0] + 1), count: counts[0] + 1)
// 주어진 n x n 배열 저장
// (n+1) x (n+1) 크기로 저장하고, 행렬의 인덱스가 0이면 0 저장
for i in 0..<counts[0] {
    arr.append([0] + readLine()!.split(separator: " ").map{ Int($0)! })
}

// dp[i][j] = 0,0 부터 i,j까지 모두 합한 결과를 저장
for i in 1..<dp.count {
    for j in 1..<dp.count {
        dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + arr[i][j]
    }
}

// 해당 범위만큼의 연산결과 출력
for i in 0..<counts[1] {
    var inputs = readLine()!.split(separator: " ").map{ Int($0)! }
    let x1 = inputs[0]
    let y1 = inputs[1]
    let x2 = inputs[2]
    let y2 = inputs[3]

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

내가 푼 풀이

- DFS 와 BFS 알고리즘으로 푼다.

- 정점이 여러개면, 접점 번호가 작은 것부터 먼저 방문한다

- DFS는 Dictionary에서 마지막원소를 빼므로 내림차순, BFS는 첫 번째 원소를 빼므로 오름차순으로 정렬한다.

import Foundation

let inputs = readLine()!.split(separator: " ").map{ Int($0)! }
var dict = [Int: [Int]]()

// 그래프 입력
for i in 0..<inputs[1] {
    let input = readLine()!.split(separator: " ").map{ Int($0)! }
    if dict[input[0]] == nil {
        dict[input[0]] = [input[1]]
    } else if !dict[input[0]]!.contains(input[1]) {
        dict[input[0]]!.append(input[1])
    }
    if dict[input[1]] == nil {
        dict[input[1]] = [input[0]]
    } else if !dict[input[1]]!.contains(input[0]) {
        dict[input[1]]!.append(input[0])
    }
}

var visitedQueue = [Int]()
var visitedQueue2 = [Int]()
var needVisitStack = [inputs[2]]

// DFS
// 인접한 접점번호가 작은순이므로, 접점번호가 저장된배열을 내림차순으로 정렬한다.
while !needVisitStack.isEmpty {
    let node = needVisitStack.removeLast()
    if visitedQueue.contains(node) { continue }
    
    visitedQueue.append(node)
    needVisitStack += dict[node]?.sorted{ $0 > $1 } ?? []
}

// BFS
// 인접한 접점번호가 작은순이므로, 접점번호가 저장된배열을 오름차순으로 정렬한다.
needVisitStack = [inputs[2]]
while !needVisitStack.isEmpty {
    let node = needVisitStack.removeFirst()
    if visitedQueue2.contains(node) { continue }
    
    visitedQueue2.append(node)
    needVisitStack += dict[node]?.sorted{ $0 < $1 } ?? []
}

print(visitedQueue.map{ String($0)}.joined(separator: " "))
print(visitedQueue2.map{ String($0)}.joined(separator: " "))

내가 푼 풀이

- 주어진 레벨을 배열로 만들었을때 원소가 중복되지 않으며, 오름차순으로 만들어야 한다.

- 주어진 배열의 인덱스순으로 난이도가 오름차순이므로, 정렬하지 않고 마지막 어려운 레벨부터 점수를 수정한다.

- 현재 레벨이 이전 레벨보다 점수가 작거나 같으면 이전레벨의 점수를 현재레벨의 점수 - 1로 바꾸고,

- 이전레벨의 점수 - 현재레벨의 점수 + 1 해준다.

- 이를 배열의 첫 번째 원소까지 모두 해주면, 원소가 중복되지 않는 오름차순으로 만들어진다.

import Foundation

let count = Int(readLine()!)!
var arr = [Int]()
var result = 0

// 레벨 점수 입력
for i in 0..<count {
    arr.append(Int(readLine()!)!)
}

// 마지막레벨부터 검사한다.
// 현재레벨이 이전레벨보다 점수가 낮거나 같으면 수정
// 이전레벨의 점수 = 현재레벨의 점수 - 1
// 점수감소횟수 = 이전레벨의 점수 - 현재레벨의 점수 + 1
for i in (1..<arr.count).reversed() {
    if arr[i] <= arr[i-1] {
        result += arr[i-1] - arr[i] + 1
        arr[i-1] = arr[i] - 1
    }
}

print(result)

- 수열이 주어졌을 때, 각 위치 인덱스에서 만들 수 있는 바이토닉 수열의 길이 최댓값을 출력한다.

- dp[i] = j : i번째 인덱스의 원소값을 기준으로 했을 때의 증가하는 수열의 길이

- rdp[i] = j : i번째 인덱스의 원소값을 기준으로 i+1 이후로 감소하는 수열의 길이

예시

arr = [1,2,1,5]

- index = 0인 원소 1이 주어졌을 때, 1 자체로 수열의 길이 1을 가진다. dp[0] = 1

- index = 1인 원소 2가 주어졌을 때, 2 자체로 수열의 길이 1을 가진다. dp[1] = 1

- arr[0] = 1은 2보다 작은 값이다.

- 인덱스 1 이전의 원소중 중복되는 작은 수가 없다. 

- dp[1] = dp[1] + 1

- index = 2인 원소 1이 주어졌을 때, 1 자체로 수열의 길이 1을 가진다. dp[2] = 1

- arr[0] = 1은 같은 값이므로 패스한다.

- arr[1] = 2는 큰 값이므로 패스한다.

- 인덱스 2 이전의 원소중 작은 값이 없다.

- index = 3인 원소 5가 주어졌을 때, 5 자체로 수열의 길이 1을 가진다. dp[3] = 1

- arr[0] = 1은 5보다 작은 값이다.

- 0번째 인덱스 이전의 값이 없으므로 dp[3] = dp[3] + 1 (dp[3] = 2)

- arr[1] = 2는 5보다 작은 값이다.

- 1번째 인덱스 이전의 값 중 2와 중복된 수가 없으므로 dp[3] = dp[3] + 1 (dp[3] = 3)

- arr[2] = 1은 5보다 작은 값이다.

- 2번째 인덱스 이전의 값 중 = arr[2] 이므로 중복된 수로 dp값을 증가시키지 않는다.

위 예시를 통해 조건을 다음과 같이 구현할 수 있다.

1. 이전 인덱스의 원소보다 큰가?

2. 이전 인덱스의 작은 원소들 중 중복되지 않는가?

dp[i] = j 라 했을 때, i번째 원소를 기준으로 증가하는 수열의 길이를 넣었으므로

중복되는지 체크하려면, dp[j] + 1 > dp[i] 이어야 한다.

위 예시에서 arr[3] = 5에서 확인할 때, 0번째 인덱스에서 이미 dp값을 증가시켰으므로 5를 기준으로 한 증가수열에 이미 1이 들어가 있다.

그러고 2번째에서 다시 1을 만났을 때, 이미 중복되므로 dp값을 증가시키지 않았다.

바이토닉수열은 어떤 수 기준으로 증가수열과 감수수열을 합친 것이므로, 위 순서를 역순으로 하면 감소하는 수열이 나온다.

증가수열 + 감소수열을 해준 후, 이는 기준이 되는 수가 중복으로 들어가 있으므로 -1을 해주고 결과 중 최댓값을 출력한다.

import Foundation

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

// 각 위치의 원소는 그 원소 하나 자체로 바이토닉 수열의 길이 1을 가진다.
// 인덱스 하나를 기준으로 이전 인덱스의 원소들을 모두 검사한다.
// 이전 원소보다 크고, 작은 원소가 중복되지않는 경우 1을 추가해준다.
for i in 0..<dp.count {
    dp[i] = 1
    for j in 0..<i {
        if arr[i] > arr[j] && dp[i] < dp[j] + 1 {
            dp[i] += 1
        }
    }
}

// 위 dp는 증가하는 수열의 길이를 구했다면, rdp는 감소하는 수열의 길이를 구하는것이다.
for i in (0..<rdp.count).reversed() {
    rdp[i] = 1
    for j in (i..<rdp.count).reversed() {
        if arr[i] > arr[j] && rdp[i] < rdp[j] + 1 {
            rdp[i] += 1
        }
    }
}

// 한 원소를 기준으로 했을때, dp rdp를 모두 구하고 더하면 기준이되는 원소가 중복으로 더해지므로 -1을 해준다.
for i in 0..<dp.count {
    dp[i] += rdp[i] - 1
}
print(dp.max()!)

내가 푼 풀이

- 팰린드롬은 주어진 문자가 뒤집어도 같은 문자가 된다면 그 문자열은 팰린드롬인 문자열이다.

- 문자열이 주어졌을때, 이것을 조합해서 만들 수 있는 팰린드롬 문자열은 1개 이상일 수 있다.

- 정답이 여러개면 사전순으로 앞서는 것을 출력한다.

- 팰린드롬인 조건을 여러 가지 생각했었는데, 단순히 만들어보기로 했다.

- 문자열이 주어졌을 때 문자로 쪼갠 후 사전순으로 오름차순으로 정렬한다.

- 문자열의 개수를 Dictonary에 저장해서 개수가 2개이상이라면 2로 나눈 몫만큼 앞뒤로 붙인다.

- 갯수가 홀수라면 문자를 붙이고도 남으니 중간위치에 넣는다.

- 주어진 문자열을 사전순으로 정렬했으니, 문자를 모두 붙여도 만약 팰린드롬 문자열이면 사전순으로 가장 앞서는 문자가 될 것이다.

- 만든 문자열을 뒤집어서 서로 비교했을 때, 같은 문자열이면 팰린드롬 문자열이므로 출력, 다르다면 "I'm Sorry Hansoo"를 출력

import Foundation

var arr = Array(readLine()!).map{ String($0) }
var dict = [String: Int]()
var first = [String]()
var middle = [String]()
var last = [String]()

// 팰린드롬 문자열은 중간을 기준으로 데칼코마니형태를 이루고있다.
// 앞 범위의 문자, 뒤 범위의 문자, 중간 기준이되는 문자 배열 3가지를 선언
// 주어진 문자열을 문자로 쪼갰을때, 문자의 갯수를 dict에 저장
for i in 0..<arr.count {
    if dict[arr[i]] == nil {
        dict[arr[i]] = 1
    } else {
        dict[arr[i]]! += 1
    }
}

// 문자의 사전순으로 정렬한다.
var sortedDict = dict.sorted{ $0.key < $1.key }

// 문자가 2개이상이면 2로 나눈 몫만큼 앞 뒤로 붙여준다.
// 붙이고 나서 문자가 남으면 중간에 붙여준다.
// 문자가 애초에 1개밖에없다면 중간에 붙여준다.
for (key, value) in sortedDict {
    if value > 1 {
        var n = value / 2
        var str = ""
        for i in 0..<n {
            str += key
        }
        first.append(str)
        last.insert(str, at: 0)
        if value % 2 != 0 {
            middle.append(key)
        }
    } else {
        middle.append(key)
        continue
    }
}

// 사전순으로 문자를 붙인 문자열을 뒤집어서 같다면 팰린드롬 문자열
var str = (first + middle + last).joined(separator: "")
if str == String(str.reversed()) {
    print(str)
} else {
    print("I'm Sorry Hansoo")
}

내가 푼 풀이

- 주어진 N의 길이의 오르막 수를 구하는 문제

- 오르막수는 수가 오름차순이면되고, 같은 번호여도 오름차순으로 친다.

- N이 1 일때, 앞자리수 0~9 는 모두 오르막수가 된다. 총 10개

- N이 2일때, 앞자리수와 같거나 큰수가 뒤에 올 수 있다.

- N이 3일때, 마지막수는 그 전의 수보다 같거나 작아야한다.

- 예시로 00 다음에 올 수는 0~9 , 05 다음에 올 수는 5~9 가된다.

- 이는 이전 앞자리 수의 오르막 수 갯수를 모두 더한것과 같다.

위를 통해 규칙을 알아 낼 수 있다.

dp[i][j] = i자리수중 앞자리수가 j일때 오르막수의 갯수 라 정의하자.

dp[3][0] = 앞자리가 0인 3자리수의 오르막수 갯수

앞자리 수 0을 제외한 두번째 자리가 0으로 시작할때의 오르막수 갯수 = dp[2][0] 

앞자리 수 0을 제외한 두번째 자리가 1로 시작할때의 오르막수 갯수 = dp[2][1]

점화식은 dp[i][j] = dp[i][j] + dp[i-1][k] ( j <= k <= 9 )

위 규칙을 통해 코드로 구현했다.

import Foundation

let count = Int(readLine()!)!
var dp = Array(repeating: Array(repeating: 0, count: 10), count: count+1)
var result = 0

// 1자리 수는 오르막수도 1개
for i in 0..<10 {
    dp[1][i] = 1
}

// i자리 수에서 앞자리가 j일때 dp[i][j] += dp[i-1][k] ( j<= k <= 9 )
if count == 1 {
    result = dp[1].reduce(0 ,+)
} else {
    for i in 2...count {
        for j in 0...9 {
            for k in j...9 {
                dp[i][j] = (dp[i][j] + dp[i-1][k]) % 10007
            }
        }
    }
    result = dp[count].reduce(0, +) % 10007
}

print(result)

내가 푼 풀이

- 처음에는 dp[n] = max(dp[n-r] + 1, dp[n]) 의 방법으로 풀었다.

- 위 방법은 동전의 구성이 같고 순서만 달라도 다른경우로 취급했을 경우의 경우의수이다.

- 문제의 핵심은 k가치인 동전으로 k보다 가치가 낮게 만들 수 없다는것이다.

- 가치가 담긴 배열을 오름차순으로 정렬후, 낮은가치부터 dp에 저장한다

- dp[n]: n원을 만들 수 있는 경우의 수

동전가치의 배열: [1,2] , dp[k]: k원을 만드는 경우의 수

1,2 가치의 동전들로 0원을 만드는 경우의 수는 동전을 사용하지않는경우 1가지이다.

dp[0] = 1

n = 1 일때, dp[2] = dp[2] + dp[2 - 1] = 1

n= 2 일때, dp[2] = dp[2] + dp[2 - 2] = dp[2] + dp[0] = 2

점화식: dp[n] = dp[n] + dp[n-현재동전의가치] ( n >= 현재 동전의가치)

import Foundation

let inputs = readLine()!.split(separator: " ").map{ Int($0)! }
var arr = [Int]()
var dp = Array(repeating: 0, count: inputs[1]+1)
for i in 0..<inputs[0] {
    arr.append(Int(readLine()!)!)
}
// 동전의 가치 오름차순으로 정렬
// 동전들로 0원을 만드는 경우의 수는 1가지 (동전을 쓰지않는방법)
arr.sort{ $0 < $1 }
dp[0] = 1

// k가치의 동전은 k보다 낮은가치를 만들 수 없다.
// 동전들마다 만들 수 있는 경우의 수를 dp에 저장한다.
// dp[n]: n원으로 만들 수 있는 경우의 수
for i in 0..<arr.count {
    for j in 0..<dp.count {
        if j-arr[i] >= 0 {
            if dp[j] + dp[j-arr[i]] >= Int(pow(2.0, 31.0)) {
                dp[j] = 0
            } else {
                dp[j] = dp[j] + dp[j-arr[i]]
            }
        }
    }
}

print(dp[inputs[1]])

문제

하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 올려놓을 수 있다.

무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 프로그램을 작성하시오.

예를 들어, 무게가 각각 3, 1, 6, 2, 7, 30, 1인 7개의 저울추가 주어졌을 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값은 21이다. 

내가 푼 풀이

- 주어진 추와 같은 무게의 물건을 잴 수 있고, 추로 잴 수 없는 무게의 최솟값을 구한다.

- 추의 무게를 오름차순으로 정렬 후, 추가 추가 될때마다 잴 수 있는 무게들을 배열에 두었다.

- 배열의 최솟값과 최댓값이 연속된다면, 잴 수 없는 무게는 최댓값+1 이 되고, 연속되지 않는다면 끊어진 무게 중 최솟값을 출력했다.

- 결과는 시간초과가 떴다.

- 연산 시간을 줄일 방법이 떠오르지 않아서, 결국 다른 사람의 풀이를 참고했다.

- 추의 무게를 오름차순으로 정렬후, 한 개씩 추가해 가며 측정할 수 있는 범위를 갱신한다.

- 추를 추가했을때 측정범위와, 이전 측정범위가 연속되지 않는다면, 이전 측정범위의 최댓값 + 1 이 측정할 수 없는 무게의 최솟값이 된다.

- 추를 모두 추가했는데 연속된다면, 측정범위의 최댓값 + 1 이 최솟값이 된다.

- 오름차순으로 정렬된 추의 첫 번째 무게가 1보다 크면, 측정할 수 없는 무게의 최솟값은 1 이 된다.

도움을 받은 글: https://aerocode.net/392

예제입력을 통해 예시를 들어보자

무게배열: [3,1,6,2,7,30,1] 이 주어졌을 때

오름차순으로 정렬하면 [1,1,2,3,6,7,30]이다.

- 무게 1을 추가했을 때

• 이전 측정범위: [0, 0]
• 추가한 측정범위: [1, 1]
• 이전 측정범위의 최댓값 + 1 >= 추가한 측정범위의 최솟값 이 성립하므로 연속된다고 볼 수 있다.
• 측정할 수 없는 무게의 최솟값: 2

- 무게 1을 추가했을 때

• 이전 측정범위: [0, 1] 
• 추가한 측정범위: [1, 2]
• 이전 측정범위의 최댓값 + 1 >= 추가한 측정범위의 최솟값 이 성립하므로 연속된다고 볼 수 있다.
• 측정할 수 없는 무게의 최솟값: 3

- 무게 2를 추가했을 때

• 이전 측정범위: [0, 2] 
• 추가한 측정범위: [2, 4]
• 이전 측정범위의 최댓값 + 1 >= 추가한 측정범위의 최솟값 이 성립하므로 연속된다고 볼 수 있다.
• 측정할 수 없는 무게의 최솟값: 5

- 무게 3을 추가했을 때

• 이전 측정범위: [0, 4] 
• 추가한 측정범위: [3, 7]
• 이전 측정범위의 최댓값 + 1 >= 추가한 측정범위의 최솟값 이 성립하므로 연속된다고 볼 수 있다.
• 측정할 수 없는 무게의 최솟값: 8

- 무게 6을 추가했을 때

• 이전 측정범위: [0, 7] 
• 추가한 측정범위: [6, 13]
• 이전 측정범위의 최댓값 + 1 >= 추가한 측정범위의 최솟값 이 성립하므로 연속된다고 볼 수 있다.
• 측정할 수 없는 무게의 최솟값: 14

- 무게 7을 추가했을 때

• 이전 측정범위: [0, 13] 
• 추가한 측정범위: [7, 20]
• 이전 측정범위의 최댓값 + 1 >= 추가한 측정범위의 최솟값 이 성립하므로 연속된다고 볼 수 있다.
• 측정할 수 없는 무게의 최솟값: 21

- 무게 30을 추가했을 때

• 이전 측정범위: [0, 20] 
• 추가한 측정범위: [30, 50]
• 이전 측정범위의 최댓값 + 1 >= 추가한 측정범위의 최솟값 이 성립하지 않는다.
• 이는 측정범위가 연속되지 않으므로 끊어진 범위중 최솟값을 구한다. [21,22,23,...,29] 중 최솟값
• 측정할 수 없는 무게의 최솟값: 21

따라서 주어진 추로 측정할 수 없는 무게의 최솟값은 21이 되는 것이다.

이를 바탕으로 코드로 구현한다.

import Foundation

let count = Int(readLine()!)!
var arr = readLine()!.split(separator: " ").map{ Int($0)! }
var rangeNum = [0,0]
var min = 0
var sortedArr = arr.sorted{ $0 < $1}

// 추의 무게가 담긴 배열을 오름차순으로 정렬한다.
// 첫번째 추의 무게가 1보다 큰 수라면 최솟값은 1이된다.
// 첫번째 추의 무게가 1이고, 추의 갯수가 1 이라면 최솟값은 2가된다.
for i in 0..<sortedArr.count {
    if i == 0 {
        if sortedArr[i] != 1 {
            min = 1
        } else {
            rangeNum = [0,1]
            min = 2
        }
    } else {
        // range는 추가된 추로 새롭게 측정할 수 있는 범위
        // rangeNum은 이전의 추로 측정할 수 있는 범위이다.
        var range = rangeNum.map{ $0 + sortedArr[i]}
        
        
        // 이전의 측정가능한범위의 최댓값+1이 새롭게 측정가능한 범위의 최솟값 보다 크거나 같다면 연속된것
        // 연속됬다면 새롭게 측정가능한 범위의 최댓값+1이 정답이 된다.
        // 반대라면 끊어진 범위중 최솟값 출력
        if rangeNum[1]+1 >= range[0] {
            rangeNum = [0, range[1]]
            min = rangeNum[1] + 1
        } else {
            min = rangeNum[1] + 1
            break
        }
    }
    
}

print(min)