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

 

11779번: 최소비용 구하기 2

첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스

www.acmicpc.net

다익스트라 알고리즘 문제다. 스위프트의 경우 heap구현이 필요하다. Rhyno님이 구현한 heap을 사용하였다.

 

풀이

입력되는 간선의 최대개수가 100,000개, 노드의 개수가 1,000개 이기에 우선순위 큐가 필수이며 메모리 초과를 유도하는 테스트 케이스가 주어지기에 다익스트라 알고리즘에 대한 정확한 이해가 필요하다. 이번 문제를 통해 조금 더 다익스트라 알고리즘에 친해졌다.

 

다익스트라 알고리즘을 통해 최단거리를 구하는데, 최단거리를 나타내는 ans배열에는 (최단거리, 진입노드) 튜플 배열로 생성하여 정보를 담아낸다. 

마지막에는 ans배열을 통해 [ 도착지점 -> 출발지점 ] 역순으로 dfs탐색을 통해 경로와 거리를 출력해 준다.

 

예제를 기준으로 설명하면 다음과 같다.

출발지점의 가중치를 0으로 변경. 시작노드는 자기자신과 동일하게 갱신했다.
1번 노드에서 갈 수 있는 간선을 탐색하여 ans[next].cost > ans[curr].cost + map[curr][next].cost 비교연산을 통해 더 작은 가중치로 ans값을 갱신한다.
ans의 값 중 가중치가 가장 작은 값으로 갱신된 노드인 4번 노드를 탐색, 5번 노드의 값을 더 줄일 수 있으므로 갱신한다.
이후 방문하지 않은 노드 중 가중치가 가장 작은 값인 2번노드를 탐색, 하지만 더 작은 값이 없기에 방문처리만 해주고 다음 노드를 탐색한다.
남아 있는 노드 중 더 작은 가중치를 가진 3번 노드 탐색, 마찬가지로 값을 갱신하지 못한 채 방문처리를 하고 마지막 5번노드로 이동
마지막 노드를 탐색 후 갱신된 ans배열.

1 2 3 4 5
0 : 1 2 : 1 3 : 1 1 : 1 4 : 4

다익스트라 알고리즘의 특성상, 매 탐색마다 가중치가 가장 작은 노드부터 탐색하기에 목적 노드를 방문 완료되면, 해당 노드의 경로는 이미 최단 경로인 것을 확신할 수 있다. 문제에서는 항상 시작 지점과 도착 지점의 경로가 있음을 보장했고, 테스트 케이스에서는 시간 초과와 메모리 초과를 유도하는 입력 값이 주어지기에 도착 노드의 방문이 확인되면 곧바로 탐색을 중단하고 갱신된 ans 배열을 통해 dfs 탐색을 수행하면 된다.

 

정답 코드

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 INF = Int.max
let N = Int(readLine()!)!
let M = Int(readLine()!)!
var map = Array(repeating: [(num:Int, cost:Int)](), count: N)
var visited = Array(repeating: false, count: N)
var ans = Array(repeating: (cost:INF,num:-1), count: N)
for _ in 0..<M{
let line = readLine()!.split(separator: " ").map{Int($0)!}
let u = line[0]-1
let v = line[1]-1
let cost = line[2]
map[u].append((v,cost))
}
let line = readLine()!.split(separator: " ").map{Int($0)!-1}
let U = line[0]
let V = line[1]
ans[U] = (0,U)
var pq = Heap<(num:Int,cost:Int)>(comparer: {$0.1>$1.1})
pq.insert((U,0))
while !pq.isEmpty{
let curr = pq.delete()!
visited[curr.num] = true
if visited[V]{ break }
for next in map[curr.num]{
if visited[next.num]{ continue }
if ans[next.num].cost > ans[curr.num].cost+next.cost{
ans[next.num] = (ans[curr.num].cost+next.cost, curr.num)
pq.insert((next.num,ans[next.num].cost))
}
}
}
var degree = 0
var path = [String]()
func dfs(from u:Int,to v:Int){
degree += 1
path.append("\(u+1)")
if u == v{
return
}
dfs(from: ans[u].num, to: v)
}
dfs(from: V, to: U)
print(ans[V].cost)
print(degree)
print(Array(path.reversed()).joined(separator: " "))
view raw 11779.swift hosted with ❤ by GitHub

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

[10830] 행렬 제곱  (0) 2023.02.11
[2638] 치즈  (0) 2023.02.10
[11444] 피보나치 수 6  (0) 2023.02.08
[17144] 미세먼지 안녕!  (0) 2023.02.07
[4836] 춤  (0) 2023.02.06

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

 

11444번: 피보나치 수 6

첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.

www.acmicpc.net

피보나치 문제다. 해당 문제 덕분에 피보나치수를 구하는 다양한 방법들 있다는 것을 알았다.

 

풀이

Fm+n=Fm−1Fn+FmFn−1

도가뉴 항등식을 이용하였다. 해당 수식을 정리하면 

 

F2n=Fn(Fn+2Fn−1)

F2n+1=Fn2+2Fn+12

위와 같은 수식을 얻을 수 있다.

해당 수식을 이용하면 기존의 피보나치수를 계산하는 방법보다 훨씬 적은 수의 호출을 통해서 값을 구할 수 있다.

 

메모리 초과를 피하기 위해 딕셔너리를 이용하여 수를 담아내었다.

 

정답 코드

import Foundation
let n = Int(readLine()!)!
var arr = Dictionary<Int,Int>()
arr[0] = 0
arr[1] = 1
func fibonacci(n:Int) -> Int{
let check = n%2==0 ? true : false
if arr[n] == nil{
if check{
let fnM1 = fibonacci(n: n/2-1)
let fn = fibonacci(n: n/2)
arr[n] = (fn*(2*fnM1+fn))%1000000007
}else{
let fnP1 = fibonacci(n: n/2+1)
let fn = fibonacci(n: n/2)
arr[n] = ((fn*fn)+(fnP1*fnP1))%1000000007
}
}
return arr[n]!
}
print(fibonacci(n: n))
view raw 11444.swift hosted with ❤ by GitHub

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

[2638] 치즈  (0) 2023.02.10
[11779] 최소비용 구하기 2  (0) 2023.02.10
[17144] 미세먼지 안녕!  (0) 2023.02.07
[4836] 춤  (0) 2023.02.06
[4485] 녹색 옷 입은 애가 젤다지?  (0) 2023.02.05

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

 

17144번: 미세먼지 안녕!

미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사

www.acmicpc.net

구현문제다.

 

풀이

문제에 주어지는 대로 먼지를 흩뿌리는 함수 spread()와 공기청정기를 가동하는 cleanClock(), cleanAntiClock() 함수를 구현하여 접근했다. spread() 함수의 경우 한 좌표의 인접좌표에 대해서 동작을 구형했고, 배열을 모두 탐색하면서 값이 0 이상이라면 함수를 수행하는 방법으로 구현했다.

공기청정기의 경우 시계/반시계 방향으로 순회하면서 값을 옮겨주는 동작을 구현하였다. 마지막으로 배열을 탐색하여 먼지의 수치를 출력하면 된다.

 

정답 코드

import Foundation
let RCT = readLine()!.split(separator: " ").map{Int($0)!}
let R = RCT[0]
let C = RCT[1]
let T = RCT[2]
var now = Array(repeating: Array(repeating: 0, count: C), count: R)
var next = now
var ap = [(Int,Int)]()
var total = 0
for i in 0..<R{
let line = readLine()!.split(separator: " ").map{Int($0)!}
for k in 0..<C{
now[i][k] = line[k]
if line[k] == -1{
ap.append((i,k))
}
}
}
func spread(x:Int, y:Int){
let dx = [-1,1,0,0]
let dy = [0,0,-1,1]
let dust = now[x][y]/5
for i in 0..<4{
let nx = x+dx[i]
let ny = y+dy[i]
if nx < 0 || nx >= R || ny < 0 || ny >= C || now[nx][ny] == -1{ continue }
next[nx][ny] += dust
now[x][y] -= dust
}
next[x][y] += now[x][y]
}
func cleanAntiClock(){
let x = ap[0].0
let y = ap[0].1
for nx in stride(from: x-1, through: 1, by: -1){
now[nx][y] = now[nx-1][y]
}
for ny in stride(from: 0, through: C-2, by: +1){
now[0][ny] = now[0][ny+1]
}
for nx in stride(from: 0, through: x-1, by: +1){
now[nx][C-1] = now[nx+1][C-1]
}
for ny in stride(from: C-1, through: 2, by: -1){
now[x][ny] = now[x][ny-1]
}
now[x][y+1] = 0
}
func cleanClock(){
let x = ap[1].0
let y = ap[1].1
for nx in stride(from: x+1, through: R-2, by: +1){
now[nx][y] = now[nx+1][y]
}
for ny in stride(from: 0, through: C-2, by: +1){
now[R-1][ny] = now[R-1][ny+1]
}
for nx in stride(from: R-1, through: x+1, by: -1){
now[nx][C-1] = now[nx-1][C-1]
}
for ny in stride(from: C-1, through: 2, by: -1){
now[x][ny] = now[x][ny-1]
}
now[x][y+1] = 0
}
for _ in 0..<T{
next = Array(repeating: Array(repeating: 0, count: C), count: R)
for i in 0..<R{
for k in 0..<C{
if now[i][k]>0{
spread(x: i, y: k)
}
}
}
next[ap[0].0][ap[0].1] = -1
next[ap[1].0][ap[1].1] = -1
now = next
cleanAntiClock()
cleanClock()
}
total = now.flatMap({$0}).filter({$0>0}).reduce(0, +)
print(total)
view raw 17144.swift hosted with ❤ by GitHub

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

[11779] 최소비용 구하기 2  (0) 2023.02.10
[11444] 피보나치 수 6  (0) 2023.02.08
[4836] 춤  (0) 2023.02.06
[4485] 녹색 옷 입은 애가 젤다지?  (0) 2023.02.05
[3048] 개미  (0) 2023.02.04

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

 

4836번: 춤

입력은 여러개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 창영이가 춘 춤이 주어진다. 각 춤은 1000스텝을 넘지 않는다. 각 스텝 알파벳 소문자로 이루어져

www.acmicpc.net

문자열 문제다. 쉽게 풀 수 있지만 문제 자체가 조금 번거롭기도 하고 꼼꼼히 보지 않으면 실수하기 쉽다. 

 

풀이

배열에 담아 각 조건을 탐색하면 된다. 1번 조건의 "dip은 jiggle을 춘 다음이나 다다음, 또는 twirl을 추기 전에 출 수 있다." 부분에서 twril이 문장 이후 아무 데나 나오면 되는 것으로 착각했다. dip 바로 뒤에 twirl이 오는지만 확인하면 된다.

 

다른 조건들의 경우 배열의 contain 메소드를 사용하여 풀어내면 된다. 단 출력할 때의 문장 포맷을 잘 확인하고 출력하자. 제대로 확인 안 해서 틀린 부분을 찾아내느라 시간을 낭비했다. 문제를 꼼꼼히 읽었는지를 요하는 문제다.

 

정답 코드

import Foundation
var ans = [String]()
while let dance = readLine(){
if dance == ""{ break }
var step = dance.split(separator: " ").map{String($0)}
var errors = [Int]()
let length = step.count
if length < 3{
errors.append(2)
}else{
let ending = step[length-3...length-1].joined(separator: " ")
if ending != "clap stomp clap"{
errors.append(2)
}
}
if step.contains("twirl") && !step.contains("hop"){
errors.append(3)
}
if step[0] == "jiggle"{
errors.append(4)
}
if !step.contains("dip"){
errors.append(5)
}
for i in 0..<length{
if step[i] == "dip"{
var flag = false
for k in i-2..<i{
if k<0 { continue }
if step[k] == "jiggle"{ flag = true}
}
if i+1 < length{
if step[i+1] == "twirl"{ flag = true}
}
if !flag{
step[i] = "DIP"
errors.append(1)
}
}
}
var res = String()
if errors.count == 0{
res = "form ok: " + dance
}else if errors.count == 1{
res = "form error "
res += "\(errors[0]): \(step.joined(separator: " "))"
}else{
res = "form errors "
errors.sort(by: <)
for i in 0..<errors.count{
res += "\(errors[i])"
if i < errors.count-2{
res += ", "
}else{
if i == errors.count-2{
res += " and "
}else{
res += ": \(step.joined(separator: " "))"
}
}
}
}
ans.append(res)
}
print(ans.joined(separator: "\n"))
view raw 4836.swift hosted with ❤ by GitHub

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

[11444] 피보나치 수 6  (0) 2023.02.08
[17144] 미세먼지 안녕!  (0) 2023.02.07
[4485] 녹색 옷 입은 애가 젤다지?  (0) 2023.02.05
[3048] 개미  (0) 2023.02.04
[14466] 소가 길을 건너간 이유 6  (0) 2023.02.03

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

 

4485번: 녹색 옷 입은 애가 젤다지?

젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주

www.acmicpc.net

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

 

풀이

너비우선탐색을 수행한다. 다익스트라 알고리즘의 특성상 우선순위 큐를 사용해서 풀어야 하지만, 문제의 N값이 크지 않기에 배열을 정렬하여 풀어도 시간초과는 피할 수 있다. 스위프트의 경우 우선순위큐를 직접 구현해야하기에 귀찮다.

 

방문여부를 저장할 2차원 visited 배열, 각 좌표에 도둑루피의 값을 담을 2차원 map 배열과 해당좌표까지의 최저 cost를 담을 2차원 cost배열을 생성한다. cost 배열은 INF로 초기화한 뒤 탐색을 수행한다. 

 

x, y, cost 정보를 담아낼 배열을 생성한다. 배열에서 cost가 가장 작은 좌표를 먼저 방문하여 (현재 좌표의 cost + 인접배열의 cost값)을 계산하여 인접배열의 cost를 더 작은 값으로 갱신한다. 다음 탐색에 cost가 가장 작은 값을 방문해야 하니 매 반복문의 마지막에는 큐를 정렬해 준다.

 

탐색이 끝나면 목적지인 cost배열의 가장 마지막 값을 출력하면 된다.

 

map 배열을 통해 cost배열의 시작점의 비용을 초기화
초록색은 현재 탐색위치, 빨간색은 큐에 담긴 좌표들이다. map배열의 값과 cost값을 사용하여 인접 배열의 값을 더 작은 값으로 갱신한다.
마지막 좌표 값이 구해지더라도 방문하지 않은 나머지 값들로 갱신될 수 있으므로 cost가 작은 순으로 탐색을 마저 수행한다.

정답 코드

import Foundation
var ans = [String]()
let INF = Int.max
var T = 1
while let line = readLine(){
if line == "0"{
break
}
let N = Int(line)!
var map = Array(repeating: Array(repeating: 0, count: N), count: N)
var cost = Array(repeating: Array(repeating: INF, count: N), count: N)
var visited = Array(repeating: Array(repeating: false, count: N), count: N)
let dx = [-1,1,0,0]
let dy = [0,0,-1,1]
var q = [(x:Int,y:Int,cost:Int)]()
for i in 0..<N{
let line = readLine()!.split(separator: " ").map{Int($0)!}
for k in 0..<N{
map[i][k] = line[k]
}
}
q.append((0,0,map[0][0]))
while !q.isEmpty{
let curr = q.removeLast()
let x = curr.x
let y = curr.y
visited[x][y] = true
cost[x][y] = min(cost[x][y], curr.cost)
for i in 0..<4{
let nx = x+dx[i]
let ny = y+dy[i]
if nx<0 || nx>=N || ny<0 || ny>=N || visited[nx][ny]{ continue }
q.append((nx,ny,cost[x][y]+map[nx][ny]))
}
q.sort(by: {$0.cost>$1.cost})
}
ans.append("Problem \(T): \(cost[N-1][N-1])")
T += 1
}
print(ans.joined(separator: "\n"))
view raw 4485.swift hosted with ❤ by GitHub

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

[17144] 미세먼지 안녕!  (0) 2023.02.07
[4836] 춤  (0) 2023.02.06
[3048] 개미  (0) 2023.02.04
[14466] 소가 길을 건너간 이유 6  (0) 2023.02.03
[14464] 소가 길을 건너간 이유 4  (0) 2023.02.01

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

 

3048번: 개미

T초가 지난 후에 개미의 순서를 출력한다. 첫 번째 개미 그룹은 왼쪽에서 오른쪽으로 움직이고, 두 번째 그룹은 반대 방향으로 움직인다.

www.acmicpc.net

문자열, 구현 문제다.

 

풀이

입력받은 개미의 알파벳과 우측 좌측을 나타내는 문자열로 튜플을 생성한다. 우측으로 향하는 개미와 좌측으로 향하는 개미의 알파벳을 붙여 튜플 배열을 생성 후, T번의 반복문을 통해 우측+좌측이 붙어있는 경우를 만나면 swap을 수행하였다.

 

정답 코드

import Foundation
let N = readLine()!.split(separator: " ").map{Int($0)!}
let N1 = N[0]
let N2 = N[1]
var res = [(String,String)]()
var ans = ""
let ant1 = readLine()!.reversed().map{String($0)}
let ant2 = readLine()!.map{String($0)}
let T = Int(readLine()!)!
for ant in ant1{
res.append((ant,"R"))
}
for ant in ant2{
res.append((ant,"L"))
}
for _ in 0..<T{
var curr = 0
while curr < res.count-1{
if res[curr].1 == "R" && res[curr+1].1 == "L"{
res.swapAt(curr, curr+1)
curr += 2
}else{
curr += 1
}
}
}
for res in res{ ans += res.0 }
print(ans)
view raw 3048.swift hosted with ❤ by GitHub

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

[4836] 춤  (0) 2023.02.06
[4485] 녹색 옷 입은 애가 젤다지?  (0) 2023.02.05
[14466] 소가 길을 건너간 이유 6  (0) 2023.02.03
[14464] 소가 길을 건너간 이유 4  (0) 2023.02.01
[1544] 사이클 단어  (0) 2023.01.30

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

 

14466번: 소가 길을 건너간 이유 6

첫 줄에 N, K, R이 주어진다. 다음 R줄에는 한 줄에 하나씩 길이 주어진다. 길은 상하좌우로 인접한 두 목초지를 잇고, r c r′ c′의 형태 (행, 열, 행, 열)로 주어진다. 각 수는 1 이상 N 이하이다.

www.acmicpc.net

그래프 탐색과 조합론으로 접근했다.

 

풀이

기본적인 그래프 탐색 문제와의 차별점은 지나가면 안 되는 간선이 주어진다는 점이다. 해당 부분을 어떻게 저장하고 핸들링할지 고민해하는 것이 이번 문제의 핵심.

 

인접행렬은 상, 하, 좌, 우로 4방향을 따져야 하므로 map[x좌표][y좌표][넘어갈 수 있는 방향 정보] 형태의 3차원 배열을 생성하였다. 즉 N*N*4 배열을 통해 너비우선탐색을 수행하여 해당 소가 방문하지 못하는 좌표에 다른 소가 있다면 문제에서 요구하는 답으로 판정하였다.

 

문제에서 요구하는 것은 길을 통해 건너야만 만날 수 있는 '쌍'을 찾는 것이니 중복을 없애기 위해 K에서 2개를 뽑는 조합 반복문을 통해 그래프탐색을 수행하였다.

 

정답 코드

import Foundation
let line = readLine()!.split(separator: " ").map{Int($0)!}
let N = line[0]
let K = line[1]
let R = line[2]
var map = Array(repeating: Array(repeating: Array(repeating: true, count: 4), count: N), count: N)
var visited = Array(repeating: Array(repeating: false, count: N), count: N)
var cows = [(Int,Int)]()
let dx = [-1,1,0,0]
let dy = [0,0,-1,1]
var ans = 0
func bfs(x:Int, y:Int){
var q = [(x,y)]
var idx = 0
visited[x][y] = true
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 !map[x][y][i] || nx<0 || nx>=N || ny<0 || ny>=N{ continue }
if !visited[nx][ny]{
visited[nx][ny] = true
q.append((nx,ny))
}
}
idx += 1
}
}
for _ in 0..<R{
let line = readLine()!.split(separator: " ").map{Int($0)!-1}
let ux = line[0]
let uy = line[1]
let vx = line[2]
let vy = line[3]
for i in 0..<4{
let nx = ux + dx[i]
let ny = uy + dy[i]
if nx == vx && ny == vy{
map[ux][uy][i] = false
}
}
for i in 0..<4{
let nx = vx + dx[i]
let ny = vy + dy[i]
if nx == ux && ny == uy{
map[vx][vy][i] = false
}
}
}
for _ in 0..<K{
let line = readLine()!.split(separator: " ").map{Int($0)!-1}
cows.append((line[0],line[1]))
}
for i in 0..<K-1{
let curr = cows[i]
visited = Array(repeating: Array(repeating: false, count: N), count: N)
bfs(x: curr.0, y: curr.1)
for p in i+1..<K{
let next = cows[p]
if !visited[next.0][next.1]{
ans += 1
}
}
}
print(ans)
view raw 14466.swift hosted with ❤ by GitHub

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

[4485] 녹색 옷 입은 애가 젤다지?  (0) 2023.02.05
[3048] 개미  (0) 2023.02.04
[14464] 소가 길을 건너간 이유 4  (0) 2023.02.01
[1544] 사이클 단어  (0) 2023.01.30
[1263] 시간 관리  (0) 2023.01.29

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

 

14464번: 소가 길을 건너간 이유 4

첫 줄에 C와 N이 주어진다. 다음 C줄에는 T1…TC가 주어지고, 그 다음 N줄에는 Aj와 Bj(Aj ≤ Bj)가 주어진다. A, B, T는 모두 최대 1,000,000,000인 음이 아닌 정수이고, 같을 수도 있다.

www.acmicpc.net

그리디 문제다. 

 

풀이

소와 닭의 이동시간을 비교해서 조건이 맞는 경우를 세는 문제다. 단, 여기서 중요한 점은 소의 이동가능시간이다. 해당 부분의 정렬 조건에 대해 생각하는 데에 오랜 시간이 걸렸다. 

 

닭 i가 소 A와 소 B 두 마리 모두 데려다줄 수 있는 경우, 둘 중 이동 가능 시간의 범위가 더 좁은 경우를 우선적으로 선택해야 선택받지 못한 소를 다음 순번의 닭이 데려다줄 가능성이 더 높아지게 된다. 즉 닭의 시간을 오름차순 정렬, 소의 이동시간이 짧은 순서 & 움직이기 시작한 시간이 오름차순으로 정렬이 되어야 한다는 이야기다.

 

소의 움직임이 완료된 시간을 기준으로 오름차순, 움직임이 완료된 시간이 같다면 움직이기 시작한 시간 기준으로 오름차순으로 정렬한 뒤, 오름차순으로 정렬된 닭의 시간을 기준으로 데려갈 수 있는 소들을 탐색하여 접근하였다.

 

정답 코드

import Foundation
let cn = readLine()!.split(separator: " ").map{Int($0)!}
let c = cn[0]
let n = cn[1]
var chicken = [Int]()
var cow = [(Int,Int)]()
var lastTime = 0
for _ in 0..<c{
chicken.append(Int(readLine()!)!)
lastTime = max(lastTime, chicken.last!)
}
for _ in 0..<n{
let info = readLine()!.split(separator: " ").map{Int($0)!}
if lastTime < info[0] { continue }
cow.append((info[0],info[1]))
}
chicken.sort(by: <)
cow.sort(by: {
if $0.1 == $1.1{
return $0.0 < $1.0
}else{
return $0.1 < $1.1
}
})
var cnt = 0
var visited = Array(repeating: false, count: cow.count)
for t in 0..<c{
let time = chicken[t]
for k in 0..<cow.count{
if !visited[k]{
let s = cow[k].0
let e = cow[k].1
if s<=time && time<=e{
cnt += 1
visited[k] = true
break
}
}
}
}
print(cnt)
view raw 14464.swift hosted with ❤ by GitHub

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

[3048] 개미  (0) 2023.02.04
[14466] 소가 길을 건너간 이유 6  (0) 2023.02.03
[1544] 사이클 단어  (0) 2023.01.30
[1263] 시간 관리  (0) 2023.01.29
[2607] 비슷한 단어  (2) 2023.01.27

+ Recent posts

티스토리툴바