분류 전체보기
-
[Python 3] BOJ - 12783 "곱셈 게임"BOJ 2021. 11. 3. 15:11
# 문제 링크 https://www.acmicpc.net/problem/12783 12783번: 곱셈 게임 주어진 숫자 카드와 사칙연산, 괄호 등을 조합하여 원하는 값을 만드는 게임이 있다. 이 게임을 좋아하는 ‘진’은 이번 IT공과대학 MT에서 이 게임을 하려고 카드를 챙겼다. 그러나 실수로 카드 www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 다이나믹 프로그래밍이라고 생각한다. 다이나믹 프로그래밍의 상태 공간을 현재 숫자가 num일 때 필요한 곱셈 카드의 최소 갯수인 dp[num]이라 정의한다. 만일, 어떤 수 k를 3개의 곱셈을 통해 만들 수가 있다면 $a_1 \ * \ a_2 * \ a_3 * a_4 = k$로 나타낼 수 있고, 각각의 수는 k의 약수가 됨을 알 수 있다. 위 그..
-
[Python 3] BOJ - 17940 "지하철"BOJ 2021. 11. 1. 19:43
# 문제 링크 https://www.acmicpc.net/problem/17940 17940번: 지하철 대학원생인 형욱이는 연구실에 출근할 때 주로 지하철을 이용한다. 지하철은 A와 B, 두 개의 회사에서 운영하고 있다. 두 회사는 경쟁사 관계로 사람들이 상대 회사의 지하철을 이용하는 것을 매 www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 0-1 BFS와 2차원 다익스트라라고 생각한다. 0-1 BFS란 그래프의 간선 가중치가 0 또는 1로만 구성되어 있을 때 최단 경로를 찾는 BFS이다. 일반 BFS와의 차이점은 간선이 0인 경로는 큐의 앞에 넣음으로서 최대한 간선의 가중치가 작도록 움직이는 것이다. 문제에서 회사가 다른 두 정점은 환승이 필요하고, 두 정점 사이의 환승 횟수는 같은 ..
-
[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의 좌측 그림은 로봇이 자기자신을 복사할 수 없는 상황에서 모든 열쇠를 찾는 경우이고, 오른쪽 그림은 로봇이 문제의 조건에 따라 자기자신을 복사할 수 있는 상황에서 모든 열쇠를 찾는 경우이다. 왼쪽의 경우 빨간색, 파란색, 초록색, 노란색 화살표 순서대로 방..