BOJ
-
[Python 3] BOJ - 5721 "사탕 줍기 대회"BOJ 2021. 8. 31. 22:48
# 문제 링크 https://www.acmicpc.net/problem/5721 5721번: 사탕 줍기 대회 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 M과 N이 주어졌다. (1 ≤ M × N ≤ 105) 다음 M개 줄에는 박스에 들어있는 사탕의 개수 N개가 주어진다. 박스에 들 www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 다이나믹 프로그래밍이라고 생각한다. 그림 1은 한 행을 기준으로 한 상태 공간 배열을 채우는 것을 나타낸다. 즉, 이 때의 상태 공간은 col[row][idx][status]이며 의미는 현재 row행을 기준으로 idx번째 열에서 status의 상태에 따라 얻을 수 있는 사탕의 최대 갯수이다. 문제의 조건에 따라 현재 열을 선..
-
[Python 3] BOJ - 1162 "도로포장"BOJ 2021. 8. 30. 12:07
# 문제 링크 https://www.acmicpc.net/problem/1162 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로가 연결하는 두 도시와 도로를 통과하 www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 2차원 다익스트라 알고리즘이라고 생각한다. 일반적으로 다익스트라 알고리즘은 1차원 배열이지만, 이 문제에는 정점과 또 다른 정보인 포장 횟수가 있으며 포장 여부에 따라 간선의 가중치가 달라지기 때문에 1차원으로 설정한다면 포장에 대한 정보를 알 수 없다. 따라서, 포장을 시키지 않는 경우를 기본적으로 검사한 후..
-
[Python 3] BOJ - 2151 "거울 설치"BOJ 2021. 8. 26. 22:36
# 문제 링크 https://www.acmicpc.net/problem/2151 2151번: 거울 설치 첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 BFS라고 생각한다. 문제를 많이 풀었다면 0-1 BFS 혹은 우선순위 큐를 이용한 BFS가 떠오를 것이다. 어느쪽으로 풀어도 정답을 도출할 수 있으나 이번 포스팅은 0-1 BFS로 풀어보겠다. 0-1 BFS에 대해 간략히 설명하자면, 일반적인 BFS에서는 간선의 모든 가중치가 1인데 반해 가중치가 0 혹은 1로만 이루어진 그래프의 ..
-
[Python 3] BOJ - 1933 "스카이라인"BOJ 2021. 8. 25. 21:26
# 문제 링크 https://www.acmicpc.net/problem/1933 1933번: 스카이라인 첫째 줄에 건물의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 N개의 건물에 대한 정보가 주어진다. 건물에 대한 정보는 세 정수 L, H, R로 나타나는데, 각각 건물의 왼쪽 x좌표, 높이, 오 www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 우선순위 큐와 정렬과 set의 적절한 사용이라고 생각한다. 고려해야 할 것이 많은 어려운 문제이다. 위 사진은 문제 링크에 있는 사진을 발췌한 것에 약간의 수정을 한 것이다. 빨간 점은 갑자기 높이가 상승했기 때문에 스카이라인의 경계가 되는 부분이며, 파란 점은 갑자기 높이가 하강했기 때문에 스카이라인의 경계가 되는 부..
-
[Python 3] BOJ - 1700 "멀티탭 스케줄링"BOJ 2021. 8. 24. 20:56
# 문제 링크 https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 그리디 알고리즘이라고 생각한다. 왜냐하면 현재 모든 구멍이 사용중이라면 어떤 하나를 뽑을 때 가장 나중에 사용할 전자기기를 뽑는 것이 최적이기 때문이다. 아주 간략한 증명은 다음과 같다. 현재 구멍이 모두 사용중이고 다음에 써야 할 전자기기를 A라고 하자. 만일 이 때 A가 구멍에 꽂혀있다면 A를 굳이 뽑아야 할 필요는 없다. 만약 A를 뽑는다면..
-
[Python 3] BOJ - 16681 "등산"BOJ 2021. 8. 20. 18:55
# 문제 링크 https://www.acmicpc.net/problem/16681 16681번: 등산 첫 번째 줄에 지도에 표시된 지점의 개수, 지점을 잇는 경로의 개수, 주환이의 거리 비례 체력 소모량, 높이 비례 성취감 획득량을 나타내는 정수 N, M, D, E가 공백을 사이에 두고 주어진다. (2 ≤ www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 대칭성을 이용하는 것이다. 문제에서 집에서 목표까지는 높이가 증가하는 방향, 목표에서 학교까지는 높이가 감소하는 방향으로 가는 조건이 있다. 따라서 학교에서 높이까지는 높이가 증가하는 방향이라고 할 수 있다. 그런데 집-목표-학교의 최소 거리는 집-목표 + 목표-학교의 각각의 최소 거리의 합보다 더 작을 수 없다. 따라서, 높이가 증가하..
-
[Python 3] BOJ - 2536 "버스 갈아타기"BOJ 2021. 8. 17. 18:57
# 문제 링크 https://www.acmicpc.net/problem/2536 2536번: 버스 갈아타기 첫 번째 줄에 수직선의 수 m과 수평선의 수 n이 빈칸을 사이에 두고 주어진다 (1 ≤ m,n ≤ 100,000). 두 번째 줄에 버스의 수 k (1 ≤ k ≤ 5,000)가 주어진다. 세 번째 줄부터 k 줄에 걸쳐 각 줄에 버스의 www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 그래프 모델링이라고 생각한다. n과 m에 비해 k가 5000으로 굉장히 작고, 문제에서 버스가 지나지 않는 곳에 출발점이 없기 때문에 다시 말해 버스까지 걸어갈 일이 없기 때문에 k만으로 문제를 풀 수 있다. 위 그림은 예제 입력 1의 상태를 나타낸 것이다. 그런데 사실 그림 1에서 버스 1과 8은 생략되..
-
[Python 3] BOJ - 10800 "컬러볼"BOJ 2021. 8. 16. 22:49
# 문제 링크 https://www.acmicpc.net/problem/10800 10800번: 컬러볼 첫 줄에는 공의 개수를 나타내는 자연수 N이 주어진다(1 ≤ N ≤ 200,000). 다음 N개의 줄 중 i번째 줄에는 i번째 공의 색을 나타내는 자연수 Ci와 그 크기를 나타내는 자연수 Si가 주어진다(1 ≤ Ci ≤ N www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 누적 합과 lower_bound, 좌표 압축의 적절한 이용이라고 생각한다. 현재 계산해야 하는 공의 색깔이 a이고 무게는 b라고 하자. 이 때, 전체 무게에서 b 이상인 공은 잡을 수 없다. 또한 b 미만이라 하더라도 a색깔인 공도 잡을 수 없기에 전체 무게에서 무게 b 이상의 공의 총 무게와 a 색깔에서 무게 b 미..