https://www.acmicpc.net/problem/1595 1595번: 북쪽나라의 도로 입력은 여러줄에 걸쳐 주어진다. 입력의 각 줄은 세 개의 양의 정수로 구성되어있는데, 각각은 차례대로 서로 다른 두 도시의 번호와 두 도시를 연결하는 도로의 길이를 의미한다. 모든 도로는 www.acmicpc.net 이 문제는 ‘트리의 지름’ 이라는 문제와 유사한 너무 well-known 풀이가 필요하다. 만약 내가 실제 코딩 테스트에서 이런 성질을 정확하게 유도해낼 수 있을까? 라고 생각해서 주변에 알고리즘 잘 하는 형에게 의견을 물어봤는데 사실 이런 건 너무 well known이라 공부하면서 꼭 알아둬야 하는 느낌? 테크닉?이라고 한다. 한창 몇 년 전 수능 수학 할 때의 로피탈 정리로 날먹하는 거라고 생각..

https://www.acmicpc.net/problem/1245 1245번: 농장 관리 첫째 줄에 정수 N(1 < N ≤ 100), M(1 < M ≤ 70)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄마다 격자의 높이를 의미하는 M개의 정수가 입력된다. 격자의 높이는 500보다 작거나 같은 음이 아닌 정수 www.acmicpc.net 문제를 간단하게 정리하면 특정 좌표에 특정 산 A의 높이가 표시되어 있는데, 둘러싸인 주변 산의 높이는 A보다 낮아야한다. 문제에서의 예제를 분석해보면 확실하게 이해할 수 있는데 8 7 4 3 2 2 1 0 1 3 3 3 2 1 0 1 2 2 2 2 1 0 0 2 1 1 1 1 0 0 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 2 2 1 1 0 0 1 ..

https://www.acmicpc.net/problem/12763 12763번: 지각하면 안 돼 1호관에서 3호관, 4호관을 거쳐 5호관으로 간다면, 3시간만에 3500원의 지출로 도착할 수 있다. (다행히 이번 수업은 휴강이었다고 합니다.) www.acmicpc.net 문제를 요약하면 건물 N개가 있는데 1번 건물에서 출발해 N번까지 시간 내에 도달하면서 최저 비용 경로를 찾고, 그때의 비용을 구하면 된다. 풀이 먼저 가중치가 있는 그래프가 주어지기 때문에 다익스트라로 접근했다. 이 때, N번 건물까지 도달할 때 시간은 제한 시간 내에 도착만 하면 되고, 비용을 최소화해야 한다. 따라서 비용으로 먼저 정렬 후, 시간 순서대로 정렬했다. static class Node implements Compara..

https://www.acmicpc.net/problem/15975 15975번: 화살표 그리기 직선위에 $N$개의 점들이 주어지고 각 점은 $N$개의 색깔 중 하나를 가진다. 편의상, 색깔은 1부터 $N$까지의 수로 표시 하고, 점들의 좌표는 모두 다르다. 각 점 $p$에 대해서, $p$에서 시작하는 직선 www.acmicpc.net 문제를 정말정말 간단하게 요약하면 직선 위에는 서로 다른 위치의 N개의 점을 가지고 있는데, 각 점 p와 거리가 가장 가까우면서 색깔이 같은 다른 점 q를 연결한 거리를 구하는데, 색깔이 하나 뿐이라 연결 못 한 점은 0의 거리를 갖는다. 모든 거리의 합을 더하면 답이다. 풀이 위치와 색깔 정보가 무작위로 주어지는데, 같은 색깔의 점과 가장 가까이 있는 다른 점과의 거리를..

https://www.acmicpc.net/problem/27972 27972번: 악보는 거들 뿐 키위새는 피아노를 잘 치고 싶었지만 악보를 볼 줄 몰랐다. 그러다 동영상 사이트에서 수열만 보고 피아노를 연주하는 동영상을 찾아냈다! 하지만 동영상에서 보여주는 수에 맞는 음을 누르자 www.acmicpc.net 음 하나를 연주할 때마다 정수 x를 악보에 쓴다. 다음 음을 연주할 때 더 낮은 음이면 x보다 작은 임의의 숫자를 쓰고, 더 높은 음이면 x보다 큰 임의의 숫자를 악보에 쓴다. 같으면 같은 숫자를 쓴다. 예시 만약 악보가 1 3 5 7 9라면 첫 번째 연주한 음에서 계속 증가했다는 의미가 된다. 음이 높으면 더 큰 숫자를 이용하기만 하면 되니깐 1 2 3 4 5로 압축할 수 있는 것이다. (1 2 ..

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 풀이 문제를 요약하면 각 마을의 학생들이 X번 마을에서 열리는 파티에 참여하고 돌아가는 길의 최단거리들을 찾고 그 최단거리 중 가장 오래 걸리는 학생의 소요 시간을 출력하면 된다. 다시 말해서 n→$X$+ $X$→n의 소요 시간의 최댓값을 구하는 것이다. 주의할 점은 단방향 그래프이기 때문에 파티로 가는 경로와 집으로 오는 경로가 다를 수 있다. 예시 3번 마을의 학..