BOJ
-
[Python 3] BOJ - 21757 "나누기"BOJ 2021. 10. 29. 22:24
# 문제 링크 https://www.acmicpc.net/problem/21757 21757번: 나누기 $N$개의 정수 수열 $A_1, A_2, \dots , A_N$이 주어진다. 수열을 각각이 연속된 네 부분으로 나누려고 한다. 단, 각 부분은 최소 하나의 수를 포함해야 한다. 또, 각 부분의 합은 모두 같아야 한다. 즉, 어 www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 누적 합과 다이나믹 프로그래밍이라고 생각한다. 우선 문제의 조건에 맞게 4등분한 구간의 합을 각각 $a_1, a_2, a_3, a_4$라고 하자. 그런데 모든 구간합의 합은 전체 수열의 합과 같다. 따라서, $a_1 + a_2 + a_3 + a_4 = 4k = s$이다. 따라서, 전체 합이 4로 나누어떨어지지 않으..
-
[Python 3] BOJ - 2786 "상근이의 레스토랑"BOJ 2021. 10. 25. 18:40
# 문제 링크 https://www.acmicpc.net/problem/2786 2786번: 상근이의 레스토랑 첫째 줄에 상근이네 레스토랑의 음식의 개수 N(2 ≤ N ≤ 500,000)이 주어진다. 다음 N개의 줄에는 각 음식의 가격 Ai와 Bi가 주어진다. (0 ≤ Ai, Bi ≤ 1,000,000,000) www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 그리디 알고리즘이라고 생각한다. 설명의 편의를 위하 물건 i가 있을때, 첫번째로 구매할 때 지불해야 하는 가격을 $a_i$, 첫번째로 구매하지 않을 때 지불해야 하는 가격을 $b_i$라고 하자. 위 그림 1의 경우를 생각해보자. 그림 1에서 첫번째로 구매하는 물건은 물음표, 첫번째가 아닌 두번째부터 다섯번째 구매하는 물건은 느낌표로..
-
[Python 3] BOJ - 5719 "거의 최단 경로"BOJ 2021. 10. 19. 22:30
# 문제 링크 https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 다익스트라와 인접 리스트를 역순으로 뒤집는 것이라 생각한다. 시작점에서 출발하여 끝점까지의 최단 경로는 여러 개 존재할 수 있기 때문에 실제 최단 경로를 찾으려 들면 시간초과를 피할 수 없을 것이다. 그런데 최단 경로라는 점을 생각했을 때 최단 경로 상에 있는 간선의 가중치의 합은 곧 끝점의 최단 거리와 같다. 위 ..
-
[Python 3] BOJ - 1581 "락스타 락동호"BOJ 2021. 10. 16. 20:36
# 문제 링크 https://www.acmicpc.net/problem/1581 1581번: 락스타 락동호 한국이 낳은 세계적인 락스타 락동호는 2007년 2월 1일 역대 최대 규모의 콘서트를 열었으며, 2007년 2월 11일에 자신의 음악세계를 세상에 알리고, 2007년 3월 4일에는 자신의 작곡 비법을 세계에 공 www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 그래프 모델링이라고 생각한다. 위 그림 1은 가능한 상태 전이를 그래프로 모델링한 것이다. 빠르게 끝나는 곡과 빠르게 시작하는 곡, 느리게 시작하는 곡과 느리게 시작하는 곡을 간선으로 이어준 형태이며 주의할 점은 FF, SS의 경우는 루프가 존재할 수 있다는 점이다. 따라서, (현재 곡의 종류, 이때까지 연주한 곡의 수, 연주..
-
[Python 3] BOJ - 17090 "미로 탈출하기"BOJ 2021. 10. 15. 21:57
# 문제 링크 https://www.acmicpc.net/problem/17090 17090번: 미로 탈출하기 크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다. 어떤 칸(r, c)에 적힌 문 www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 다이나믹 프로그래밍이라고 생각한다. 상태 공간을 현재 (x, y)일 때 밖으로 나갈 수 있는지 여부로 정의한다. 위 그림 1은 예제 4의 경우를 나타낸 그림이다. 빨간색이 현재 위치, 파란색 위치가 다음 위치일 때 상태이다. 만일 현재 위치를 한번도 방문하지 않는다면 -1, 처음 방문한다면 0으로 초기화한다. 만일 범위 밖으로 나..
-
[Python 3] BOJ - 1944 "복제 로봇"BOJ 2021. 10. 10. 22:37
# 문제 링크 https://www.acmicpc.net/problem/1944 1944번: 복제 로봇 첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어 www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 최소 스패닝 트리과 그래프 탐색이라고 생각한다. 위 그림 1의 좌측 그림은 로봇이 자기자신을 복사할 수 없는 상황에서 모든 열쇠를 찾는 경우이고, 오른쪽 그림은 로봇이 문제의 조건에 따라 자기자신을 복사할 수 있는 상황에서 모든 열쇠를 찾는 경우이다. 왼쪽의 경우 빨간색, 파란색, 초록색, 노란색 화살표 순서대로 방..
-
[Python 3] BOJ - 2233 "사과나무"BOJ 2021. 10. 9. 20:56
# 문제 링크 https://www.acmicpc.net/problem/2233 2233번: 사과나무 첫째 줄에 정점의 개수 N(1≤N≤2,000)이 주어진다. 둘째 줄에는 벌레가 만드는 2×N자리의 이진수가 주어진다. 셋째 줄에는 썩은 사과의 위치를 나타내는 두 정수 X, Y가 주어진다. 이는 2×N자리의 www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 스택과 LCA라고 생각한다. 크게 보면 문제는 트리를 만들고 썩은 두 사과의 LCA를 파악하는 두 단계로 나누어져있다. 위 그림 1은 스택을 이용하여 트리를 구현하는 그림이다. 문제에서 제시한 바에 따라 0이라면 현재 가리키는 노드가 처음 진입하는 의미이기 때문에 그대로 스택에 추가한다. 위 그림 2는 리프 노드인 C까지 진행된 과정을..
-
[Python 3] BOJ - 6988 "타일 밟기"BOJ 2021. 9. 30. 21:38
# 문제 링크 https://www.acmicpc.net/problem/6988 6988번: 타일 밟기 첫째 줄에는 타일의 개수 N이 주어진다. N은 3 이상 3,000 이하이다. 둘째 줄에는 N개의 타일에 적힌 자연수들이 증가하는 순서로 빈칸을 사이에 두고 주어진다. 타일에 적힌 자연수들은 각각 1,000,0 www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 다이나믹 프로그래밍이라 생각한다. 상태 공간을 dp[i][j], 현재 i번째 인덱스에서 j번째 인덱스로 타일을 밟을 때 얻을 수 있는 점수의 최대라고 정의한다. 위 그림 1에서 빨간색으로 칠한 두 숫자를 보자. 두 숫자의 차이는 2이며 그 다음에 밟을 타일의 숫자가 5로 정해지게 된다. 위 배열에서 5는 존재하기 때문에 현재 0에서..