https://www.acmicpc.net/problem/1504

 

1504번: 특정한 최단 경로

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존

www.acmicpc.net

다익스트라 알고리즘 문제. 마찬가지로 Rhyno님이 작성한 힙을 사용했다.

 

풀이

1번에서 n번 정점까지의 최단경로, 하지만 반드시 두지점을 거쳐야 한다는 조건이 붙었다.

[1 -> v1 -> v2 -> n ] 또는 [1 -> v2 -> v1 -> n] 두 가지 최단 경로중 가중치가 더 적은 경로를 반환하면 된다. 1번 정점에서 각 정점으로 향하는 최단경로, v1 정점에서 각 정점으로 향하는 최단경로, v2 정점에서 각 정점으로 향하는 최단경로 총 다익스트라 3번을 돌린 뒤 각 가중치를 적절히 조합해서 반환하면 된다.

 

하지만 여기서 경로가 없는 조건에 대해 처리해주어야 하므로 이 부분만 신경 써준다면 정답을 받을 수 있다. 본인의 경우 최단경로를 담은 배열을 -1로 초기화한뒤 다익스트라를 통해 갱신하였는데, 아무리 조건을 신경 써서 제출해도 오답판정을 받아 결국 계산 가능한 가중치의 최댓값인 2억으로 초기화하며 예외처리하였다.

 

정답 코드

import Foundation
//by rhyno
public struct Heap<T> {
var nodes: [T] = []
let comparer: (T,T) -> Bool
var isEmpty: Bool {
return nodes.isEmpty
}
init(comparer: @escaping (T,T) -> Bool) {
self.comparer = comparer
}
func peek() -> T? {
return nodes.first
}
mutating func insert(_ element: T) {
var index = nodes.count
nodes.append(element)
while index > 0, !comparer(nodes[index],nodes[(index-1)/2]) {
nodes.swapAt(index, (index-1)/2)
index = (index-1)/2
}
}
mutating func delete() -> T? {
guard !nodes.isEmpty else {
return nil
}
if nodes.count == 1 {
return nodes.removeFirst()
}
let result = nodes.first
nodes.swapAt(0, nodes.count-1)
_ = nodes.popLast()
var index = 0
while index < nodes.count {
let left = index * 2 + 1
let right = left + 1
if right < nodes.count {
if comparer(nodes[left], nodes[right]),
!comparer(nodes[right], nodes[index]) {
nodes.swapAt(right, index)
index = right
} else if !comparer(nodes[left], nodes[index]){
nodes.swapAt(left, index)
index = left
} else {
break
}
} else if left < nodes.count {
if !comparer(nodes[left], nodes[index]) {
nodes.swapAt(left, index)
index = left
} else {
break
}
} else {
break
}
}
return result
}
}
extension Heap where T: Comparable {
init() {
self.init(comparer: <)
}
}
let ne = readLine()!.split(separator: " ").map{Int($0)!}
let n = ne[0]
let e = ne[1]
var map = Array(repeating: [(Int,Int)](), count: n)
for _ in 0..<e{
let info = readLine()!.split(separator: " ").map{Int($0)!}
let u = info[0]-1
let v = info[1]-1
let cost = info[2]
map[u].append((v,cost))
map[v].append((u,cost))
}
func dij(from a:Int) -> [Int]{
var visited = Array(repeating: false, count: n)
var result = Array(repeating: 200000001, count: n)
var q = Heap<(Int,Int)>(comparer: { $0.1 > $1.1 })
result[a] = 0
q.insert((a,0))
while !q.isEmpty{
let curr = q.delete()!
let idx = curr.0
if !q.isEmpty && visited[idx] { continue }
visited[idx] = true
for next in map[idx]{
if result[next.0] > result[idx]+next.1{
result[next.0] = result[idx]+next.1
q.insert((next.0,result[next.0]))
}
}
}
return result
}
let targets = readLine()!.split(separator: " ").map{Int($0)!-1}
let curr = dij(from: 0)
let u = dij(from: targets[0])
let v = dij(from: targets[1])
var ans1 = curr[targets[0]] + u[targets[1]] + v[n-1]
var ans2 = curr[targets[1]] + v[targets[0]] + u[n-1]
var ans = min(ans1, ans2)
print(ans>=200000001 ? -1:ans)
view raw 1504.swift hosted with ❤ by GitHub

'Problem Solving > BOJ' 카테고리의 다른 글

[14246] K보다 큰 구간  (0) 2023.01.12
[2018] 수들의 합 5  (0) 2023.01.11
[1238] 파티  (0) 2023.01.04
[2056] 작업  (0) 2023.01.02
[14567] 선수과목  (0) 2023.01.01

https://www.acmicpc.net/problem/1238

 

1238번: 파티

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어

www.acmicpc.net

다익스트라 알고리즘으로 접근한 문제다. 힙 구현이 필요하다. 직접 구현할 역량이 안되기에, Rhyno님이 작성한 힙을 사용하였다.

 

풀이

간선과 가중치를 입력받은 map 배열을 통해, 다익스트라 알고리즘을 사용한다. 양방향 간선이 아닌 단방향 간선이기에 우선 파티 장소 x에서 각 마을로 되돌아가는 배열을 생성, 다익스트라 알고리즘을 통해 각 인덱스에 저장. 이후 1 ~ n번 마을에서 x로 향하는 최단거리를 한 번 더 다익스트라 알고리즘을 통해 방금 저장한 배열에 추가시켜 준다. 마지막으로 배열에 담긴 최댓값을 출력한다.

 

정답 코드

import Foundation
//heap by rhyno
public struct Heap<T> {
var nodes: [T] = []
let comparer: (T,T) -> Bool
var isEmpty: Bool {
return nodes.isEmpty
}
init(comparer: @escaping (T,T) -> Bool) {
self.comparer = comparer
}
func peek() -> T? {
return nodes.first
}
mutating func insert(_ element: T) {
var index = nodes.count
nodes.append(element)
while index > 0, !comparer(nodes[index],nodes[(index-1)/2]) {
nodes.swapAt(index, (index-1)/2)
index = (index-1)/2
}
}
mutating func delete() -> T? {
guard !nodes.isEmpty else {
return nil
}
if nodes.count == 1 {
return nodes.removeFirst()
}
let result = nodes.first
nodes.swapAt(0, nodes.count-1)
_ = nodes.popLast()
var index = 0
while index < nodes.count {
let left = index * 2 + 1
let right = left + 1
if right < nodes.count {
if comparer(nodes[left], nodes[right]),
!comparer(nodes[right], nodes[index]) {
nodes.swapAt(right, index)
index = right
} else if !comparer(nodes[left], nodes[index]){
nodes.swapAt(left, index)
index = left
} else {
break
}
} else if left < nodes.count {
if !comparer(nodes[left], nodes[index]) {
nodes.swapAt(left, index)
index = left
} else {
break
}
} else {
break
}
}
return result
}
}
extension Heap where T: Comparable {
init() {
self.init(comparer: <)
}
}
let nmx = readLine()!.split(separator: " ").map{Int($0)!}
let n = nmx[0]
let m = nmx[1]
let x = nmx[2]-1
var map = Array(repeating: [(Int,Int)](), count: n)
for _ in 0..<m{
let info = readLine()!.split(separator: " ").map{Int($0)!}
let u = info[0]-1
let v = info[1]-1
let cost = info[2]
map[u].append((v,cost))
}
for i in 0..<n{
map[i].sort(by: { $0.1 < $1.1 })
}
func dij(from a:Int) -> [Int]{
var q = Heap<(Int,Int)>(comparer: { $0.1 > $1.1 })
var visited = Array(repeating: false, count: n)
var result = Array(repeating: -1, count: n)
result[a] = 0
q.insert((a,0))
while !q.isEmpty{
let curr = q.delete()!
let idx = curr.0
if !q.isEmpty && visited[idx]{ continue }
visited[idx] = true
for next in map[idx]{
if (result[next.0] == -1) || (result[next.0] > result[idx] + next.1){
result[next.0] = result[idx] + next.1
q.insert((next.0,result[next.0]))
}
}
}
return result
}
var ans = dij(from: x)
for i in 0..<n{
ans[i] += dij(from: i)[x]
}
print(ans.max()!)
view raw 1238.swift hosted with ❤ by GitHub

'Problem Solving > BOJ' 카테고리의 다른 글

[2018] 수들의 합 5  (0) 2023.01.11
[1504] 특정한 최단 경로  (0) 2023.01.04
[2056] 작업  (0) 2023.01.02
[14567] 선수과목  (0) 2023.01.01
[1584] 게임  (0) 2022.12.30

https://www.acmicpc.net/problem/2056

 

2056번: 작업

수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해

www.acmicpc.net

위상정렬과 동적계획법으로 접근가능한 문제다.

 

풀이법

처음에는 단순히 위상정렬을 통해 큐에 접근할 때마다 가장 오래 걸린 작업시간들을 더하면 될 것이라 생각했다. 하지만 해당방법은 틀린 방법이 다.

후속이 없는 작업의 경우, 다음 탐색에  영향을 끼치지 않아야 하는데, 처음생각한 방법은 이러한 부분을 제외시키지 못했다. 따라서 해당 작업을 완료하는데 걸리는 총시간을 담은 dp 배열을 생성한 뒤, 동적계획법으로 접근해야 한다. next는 다음 작업, curr는 현재작업을 의미할 때, 점화식은 다음과 같다. 여기서 time배열은 순수 작업시간을 의미한다.

dp[next] = max(dp[next], dp[curr]+time[next])

위상정렬을 통한 그래프탐색 이후, dp배열의 최댓값을 출력하면 된다.

 

정답 코드

import Foundation
let n = Int(readLine()!)!
var map = Array(repeating: [Int](), count: n)
var time = Array(repeating: 0, count: n)
var ans = Array(repeating: 0, count: n)
var degree = Array(repeating: 0, count: n)
var q = [Int]()
for i in 0..<n{
let info = readLine()!.split(separator: " ").map{Int($0)!}
time[i] = info[0]
degree[i] = info[1]
if info[1]==0{
q.append(i)
}else{
for k in 2..<info.count{
map[info[k]-1].append(i)
}
}
}
ans = time
while !q.isEmpty{
var dq = q
q.removeAll()
for _ in 0..<dq.count{
let curr = dq.removeLast()
for next in map[curr]{
degree[next] -= 1
ans[next] = max(ans[next], ans[curr]+time[next])
if degree[next]==0{
q.append((next))
}
}
}
}
print(ans.max()!)
view raw 2056.swift hosted with ❤ by GitHub

'Problem Solving > BOJ' 카테고리의 다른 글

[1504] 특정한 최단 경로  (0) 2023.01.04
[1238] 파티  (0) 2023.01.04
[14567] 선수과목  (0) 2023.01.01
[1584] 게임  (0) 2022.12.30
[25587] 배수로  (0) 2022.12.29

https://www.acmicpc.net/problem/14567

 

14567번: 선수과목 (Prerequisite)

3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다.

www.acmicpc.net

위상정렬 문제다.

 

풀이

문제에서 요구하는 것은 선수과목의 순서가 아니라 각 과목을 듣기 위한 최소 학기수.

즉 위상정렬을 사용하여 큐에 몇번 접근하는지를 파악하면 된다. 

입력되는 값을 통해 각 노드의 진입차수를 저장. 진입차수가 0인 노드를 큐에 담아놓고 그래프탐색을 수행하면 된다.

그래프탐색을 통해 다른 노드로 진입시, 해당노드의 진입차수를 하나씩 차감. 0이 된다면 다음 탐색큐에 추가하면 된다.

문제의 정답을 계산하기 위해 반복문을 구분하여 탐색해야 한다. 해당 부분은 코드르 보는 게 이해하기 쉬울 것이다.

 

정답 코드

import Foundation
let nm = readLine()!.split(separator: " ").map{Int($0)!}
let n = nm[0]
let m = nm[1]
var map = Array(repeating: [Int](), count: n)
var arr = Array(repeating: 0, count: n)
var ans = Array(repeating: 1, count: n)
for _ in 0..<m{
let info = readLine()!.split(separator: " ").map{Int($0)!-1}
let u = info[0]
let v = info[1]
map[u].append(v)
arr[v] += 1
}
var q = [Int]()
var idx = 0
var semester = 2
for i in 0..<n{
if arr[i]==0{ q.append(i) }
}
while idx < q.count{
for _ in 0..<q.count-idx{
let curr = q[idx]
for next in map[curr]{
arr[next] -= 1
if arr[next]==0{
q.append(next)
ans[next] = semester
}
}
idx += 1
}
semester += 1
}
for ans in ans{
print(ans, terminator: " ")
}
view raw 14567.swift hosted with ❤ by GitHub

'Problem Solving > BOJ' 카테고리의 다른 글

[1238] 파티  (0) 2023.01.04
[2056] 작업  (0) 2023.01.02
[1584] 게임  (0) 2022.12.30
[25587] 배수로  (0) 2022.12.29
[2350] 대운하  (0) 2022.12.25

https://www.acmicpc.net/problem/1584

 

1584번: 게임

첫째 줄에 위험한 구역의 수 N이 주어진다. 다음 줄부터 N개의 줄에는 X1 Y1 X2 Y2와 같은 형식으로 위험한 구역의 정보가 주어진다. (X1, Y1)은 위험한 구역의 한 모서리이고, (X2, Y2)는 위험한 구역의

www.acmicpc.net

다익스트라 알고리즘으로 접근한 문제다.

 

풀이

출발지와 목적지가 이미 정해져 있는 문제이므로 거리정보를 담아둘 배열을 생성. 최대 비용 250000(500*500) 보다 큰 250001로 초기화시켜 둔다. 출발지 (0,0)은 이미 도착한 것이므로 비용을 0으로 시작. 너비우선탐색을 수행하여 비용이 더 적게 드는 경우 비용을 갱신하고 해당 좌표를 큐에 담아 탐색을 수행하면 된다. 탐색이 끝나면 가장 마지막 위치의 비용을 출력하면 된다.

 

정답 코드

import Foundation
var map = Array(repeating: Array(repeating: 0, count: 501), count: 501)
var dist = Array(repeating: Array(repeating: 250001, count: 501), count: 501)
dist[0][0] = 0
for _ in 0..<Int(readLine()!)!{
let info = readLine()!.split(separator: " ").map{Int($0)!}
let x1 = info[0]
let y1 = info[1]
let x2 = info[2]
let y2 = info[3]
for i in min(x1, x2)...max(x1, x2){
for k in min(y1, y2)...max(y1, y2){
map[i][k] = 1
}
}
}
for _ in 0..<Int(readLine()!)!{
let info = readLine()!.split(separator: " ").map{Int($0)!}
let x1 = info[0]
let y1 = info[1]
let x2 = info[2]
let y2 = info[3]
for i in min(x1, x2)...max(x1, x2){
for k in min(y1, y2)...max(y1, y2){
map[i][k] = 2
}
}
}
func bfs(){
var q = [(0,0)]
var idx = 0
let dx = [-1,1,0,0]
let dy = [0,0,-1,1]
while idx < q.count{
let curr = q[idx]
let x = curr.0
let y = curr.1
for i in 0..<4{
let nx = x+dx[i]
let ny = y+dy[i]
if nx<0 || nx>500 || ny<0 || ny>500 || map[nx][ny]==2{ continue }
if dist[nx][ny] > dist[x][y] + map[nx][ny]{
dist[nx][ny] = dist[x][y] + map[nx][ny]
q.append((nx,ny))
}
}
idx += 1
}
}
bfs()
print(dist[500][500]==250001 ? -1:dist[500][500])
view raw 1584.swift hosted with ❤ by GitHub

'Problem Solving > BOJ' 카테고리의 다른 글

[2056] 작업  (0) 2023.01.02
[14567] 선수과목  (0) 2023.01.01
[25587] 배수로  (0) 2022.12.29
[2350] 대운하  (0) 2022.12.25
[15991] 1, 2, 3 더하기 6  (0) 2022.12.24

https://www.acmicpc.net/problem/25587

 

25587번: 배수로

ChAOS 나라에는 총 $N$개의 도시가 있고 각각 $1, 2, 3, …, N$번 도시라고 부른다. ChAOS 나라에 각 도시에는 홍수를 막기 위해 배수로가 설치되어 있다. $i$번 도시의 배수로는 강수량이 $A_i$이하일 때

www.acmicpc.net

유니온 파인드 문제다. 푸는데 시간이 좀 걸렸다.

 

풀이

루트여부 및 원소의 크기정보, 배수로 용량, 강수량 정보를 담은 원소 n개의 배열을 생성하여 유니온 파인드를 수행한다. 여기서 중요한 점은 쿼리입력을 받을 때, 중간마다 출력을 요구한다는 점이다.

처음에는 출력을 요구하는 2가 입력될 때마다 배열을 전부 탐색하여 루트노드를 만나면, 홍수여부를 체크한 뒤 원소의 개수만큼 개수를 계산하여 출력하였으나, 시간초과를 받았다.

보통 시간복잡도를 계산할 때 1초당 1억 연산으로 따진다. 쿼리가 전부 2라면, 배열의 최댓값*쿼리 최댓값(100000*100000)으로 시간초과는 당연한 결과였다. 

따라서 생각해낸 풀이는 처음 정보가 주어지고 나면 배열을 탐색해 홍수가 나는 지역의 개수를 전역변수로 파악. 이후 유니온이 일어날 때마다 해당 지역이 홍수가 일어나는지, 일어나지 않는지를 파악해 전역변수를 갱신하는 것으로 접근하였더니 시간초과를 피할 수 있었다.

 

정답 코드

import Foundation
let nm = readLine()!.split(separator: " ").map{Int($0)!}
let n = nm[0]
let m = nm[1]
var arr = Array(repeating: (-1,0,0), count: n)
var flag = false
var cnt = 0
let size = readLine()!.split(separator: " ").map{Int($0)!}
for i in 0..<n{
arr[i].1 = size[i]
}
let rain = readLine()!.split(separator: " ").map{Int($0)!}
for i in 0..<n{
arr[i].2 = rain[i]
}
for i in 0..<n{
if arr[i].1 < arr[i].2{ cnt -= arr[i].0}
}
func root(of a:Int)->Int{
if arr[a].0 < 0 {return a}
arr[a].0 = root(of: arr[a].0)
return arr[a].0
}
func union(a:Int, b:Int){
let rootA = root(of: a)
let rootB = root(of: b)
if rootA == rootB {return}
if arr[rootA].1 < arr[rootA].2{ cnt += arr[rootA].0 }
if arr[rootB].1 < arr[rootB].2{ cnt += arr[rootB].0 }
arr[rootA].0 += arr[rootB].0
arr[rootB].0 = rootA
arr[rootA].1 += arr[rootB].1
arr[rootA].2 += arr[rootB].2
if arr[rootA].1 < arr[rootA].2{ cnt -= arr[rootA].0 }
}
for _ in 0..<m{
let info = readLine()!.split(separator: " ").map{Int($0)!}
let c = info[0]
if c == 2{
print(cnt)
}else{
let u = info[1]-1
let v = info[2]-1
union(a: u, b: v)
}
}
view raw 25587.swift hosted with ❤ by GitHub

언제쯤이면 고수가 될 수 있을까..

'Problem Solving > BOJ' 카테고리의 다른 글

[14567] 선수과목  (0) 2023.01.01
[1584] 게임  (0) 2022.12.30
[2350] 대운하  (0) 2022.12.25
[15991] 1, 2, 3 더하기 6  (0) 2022.12.24
[2232] 지뢰  (0) 2022.12.21

https://www.acmicpc.net/problem/2350

 

2350번: 대운하

입력의 첫 번째 줄에는 도시의 수 N, 운하의 수 M, 노선의 수 K가 주어진다. (N ≤ 1000, M ≤ 100000, K ≤ 10000) 다음 M개의 줄에는 세 정수 i, j, w가 주어지며, 이는 도시 i와 j 사이에 폭이 w인 운하를

www.acmicpc.net

[2610] 회의준비와 결이 비슷한 문제다. 

 

풀이

유니온파인드와 그래프탐색으로 접근했다. 가중치가 큰 순으로 간선을 정렬한 뒤 순서대로 유니온을 수행, 루트가 같다면 결합하지 않는다.

이후 입력되는 출발지와 도착지를 기준으로 너비우선탐색을 수행. 그래프를 탐색하면서 가중치를 수정해나가면 된다. 

 

처음에는 (k횟수만큼) 그래프와 루트정보를 매번 초기화하고, 입력되는 출발지와 도착지를 기준으로 유니온을 하면서 그래프를 탐색했으나, 시간초과발생. 생각해보니 간선을 한 번만 탐색하고도 cost를 출력할 수 있게 접근이 가능했었다.

 

정답 코드

import Foundation
let nmk = readLine()!.split(separator: " ").map{Int($0)!}
let n = nmk[0]
let m = nmk[1]
let k = nmk[2]
var arr = Array(repeating: -1, count: n)
var map = Array(repeating: [(Int,Int)](), count: n)
var edges = [(Int,Int,Int)]()
var ans = ""
func root(of a:Int) -> Int{
if arr[a] < 0{ return a}
arr[a] = root(of: arr[a])
return arr[a]
}
func union(a:Int, b:Int) -> Bool{
let rootA = root(of: a)
let rootB = root(of: b)
if rootA == rootB {return false}
arr[rootB] = rootA
return true
}
func bfs(from a:Int, to b:Int){
var visited = Array(repeating: false, count: n)
visited[a] = true
var q = [(a,201)]
var idx = 0
while idx<q.count{
let curr = q[idx].0
let cost = q[idx].1
if curr == b{
ans += "\(cost)\n"
return
}
for next in map[curr]{
if !visited[next.0]{
visited[next.0] = true
q.append((next.0,min(cost, next.1)))
}
}
idx += 1
}
}
for _ in 0..<m{
let info = readLine()!.split(separator: " ").map{Int($0)!}
let edge = (info[0]-1,info[1]-1,info[2])
edges.append(edge)
}
edges.sort(by: { $0.2>$1.2 })
for edge in edges {
let u = edge.0
let v = edge.1
let cost = edge.2
if union(a: u, b: v){
map[u].append((v,cost))
map[v].append((u,cost))
}
}
for _ in 0..<k{
let info = readLine()!.split(separator: " ").map{Int($0)!-1}
bfs(from: info[0], to: info[1])
}
print(ans)
view raw 2350.swift hosted with ❤ by GitHub

'Problem Solving > BOJ' 카테고리의 다른 글

[1584] 게임  (0) 2022.12.30
[25587] 배수로  (0) 2022.12.29
[15991] 1, 2, 3 더하기 6  (0) 2022.12.24
[2232] 지뢰  (0) 2022.12.21
[2143] 두 배열의 합  (0) 2022.12.20

https://www.acmicpc.net/problem/15991

 

15991번: 1, 2, 3 더하기 6

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.

www.acmicpc.net

다이나믹 프로그래밍 문제다.

 

풀이

우선 1부터 6까지 1,2,3을 이용한 대칭 수식을 생각하면 점화식을 위한 조건이 만들어진다.

7부터는 앞서 생각한 경우의 수식에 양쪽으로 1+...+1, 2+...+2, 3+...+3의 형태로 대칭으로 늘려나가면 된다.

즉 dp[num] = dp[num-2] + dp[num-4] + dp[num-6]이라는 점화식을 세울 수 있다.

7부터 100,000까지 반복문을 돌려 정답배열을 만든후 입력값을 인덱스로 정답을 출력하면 된다.

 

정답 코드

import Foundation
let t = Int(readLine()!)!
var dp = Array(repeating: 0, count: 100001)
dp[1] = 1 //1
dp[2] = 2 //1+1, 2
dp[3] = 2 //1+1+1, 3
dp[4] = 3 //1+1+1+1, 1+2+1, 2+2,
dp[5] = 3 //1+1+1+1+1, 1+3+1, 2+1+2
dp[6] = 6 //1+1+1+1+1+1, 1+1+2+1+1, 1+2+2+1, 2+2+2, 2+1+1+2, 3+3
for i in 7..<100001{
dp[i] = (dp[i-2]+dp[i-4]+dp[i-6])%1000000009
}
for _ in 0..<t{
let n = Int(readLine()!)!
print(dp[n])
}
view raw 15991.swift hosted with ❤ by GitHub

점화식을 세우는건 항상 어렵다..,

'Problem Solving > BOJ' 카테고리의 다른 글

[25587] 배수로  (0) 2022.12.29
[2350] 대운하  (0) 2022.12.25
[2232] 지뢰  (0) 2022.12.21
[2143] 두 배열의 합  (0) 2022.12.20
[2610] 회의준비  (0) 2022.12.19

+ Recent posts

티스토리툴바