백준

문제 링크 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 문제 풀이 단순한 다익스트라 문제인 줄 알았는데 예상치 못한 예외가 자꾸 튀어나와 낮은 정답률이 이해되는 문제였습니다. 실패 풀이) 처음에 실패했던 풀이는 최소비용 구하기2 문제처럼 route 배열을 따로 두고 이동경로를 매번 저장하는 방식이었습니다. route를 갱신하며 할당하기 때문에 문제가 없을 줄 알았으나 메모리 초과로 인해 실패했습니..

문제 링크 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 문제 풀이 최소비용 구하기 문제가 최소 비용만을 출력하는 것이었다면, 이 문제에서는 최소 비용으로 도착점에 가는 루트에 있는 모든 노드를 출력해야 합니다. 이를 위해, 이동 경로에 있는 노드들을 저장할 route라는 2차원 배열을 선언하였습니다. route배열에서 현재 노드에 대한 인덱스값은 현재 노드까지 이동하기 위한 최소 비용 루트에 포함된 노드 배..

문제 링크 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 문제 풀이 한 지점에서 다른 특정 지점까지의 최단 거리를 구하는 문제로 heapq를 통한 다익스트라 알고리즘을 구현하여 풀이했습니다. from heapq import heappush, heappop import sys input = sys.stdin.readline def dijkstra(start): q = [] distance[start - 1] =..

문제 링크 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 문제 풀이 처음에는 단순히 진실을 아는 사람과 참석 인원 중 교집합이 없는 파티를 구하면 되는 것 아닌가 하고 간단히 생각했습니다. 하지만 그렇게 생각하면 예제 입력 4번부터 출력이 다르게 됩니다. 문제에서 주어진 조건은 지민이가 거짓말쟁이로 알려지지 않으면서, 과장된 이야기를 할 수 있는 파티 개수를 구하는 것이었습니다. 만약, 1번 친구가 진실을 모른다고 1번 친구만 있는 파티에서 거짓말을 했..

문제 링크 https://www.acmicpc.net/problem/15591 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net 문제 풀이 한 노드와 다른 노드 사이의 usado가 그 사이의 usado의 최솟값이라는 조건을 보고 처음에는 해당 조건을 활용해서 usado들을 모두 저장해놓고 결과를 구해야하나 했습니다. 그것보다는 bfs를 활용하여 노드를 하나씩 이동하며 usado를 최솟값으로 갱신하고 k보다 usado가 클 경우 결괏값을 1씩 증가시키는 것이 효율..

문제 링크 https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 문제 풀이 fun main() = with(System.`in`.bufferedReader()) { val (n, k) = readLine().split(" ").map { it.toInt() } val temperature = readLine().split(" ").map { it.toInt() }.toIntArray() var sum = temperature.slice(..

문제 링크 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 풀이 fun main() = with(System.`in`.bufferedReader()) { val n = readLine().toInt() val times = Array(n) { Array(2) { 0 } } repeat(n) { val line = readLine().split(" ") times[it][0] = line[0].toInt() times[it][1] = line[1].toInt() } times.sortWith(compareBy { it[1] }.thenBy { it[0] }..

문제 링크 https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 문제 풀이 import kotlin.math.max fun main() = with(System.`in`.bufferedReader()) { val n = readLine().toInt() val weights = Array(n) { 0 } for (i in 0..< n) { weights[i] = readLine().toInt() } weights.sort() var maxW..