BOJ
-
[Python 3] BOJ - 16565 "N포커"BOJ 2021. 11. 21. 19:34
# 문제 링크 https://www.acmicpc.net/problem/16565 16565번: N포커 첫째 줄에 N장의 카드를 뽑았을 때, 플레이어가 이기는 경우의 수를 10,007로 나눈 나머지를 출력하라. www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 다이나믹 프로그래밍이라고 생각한다. 승리하는 조건은 포카드가 최소 한번 이상 일어나는 것이다. 예를 들어, 현재 뽑아야 하는 카드 갯수가 9개라면, 포카드가 1번 일어나는 경우 혹은 포카드가 2번 일어나는 경우 모두 승리하는 것이다. 따라서 남은 카드는 절대로 포카드가 되어서는 안된다. 따라서 상태 공간을 현재까지 뽑은 카드수가 cnt, 현재까지 뽑은 카드의 종류(번호 기준)가 kind라고 할 때 포카드가 되지 않는 경우의 수인 d..
-
[Python 3] BOJ - 2478 "자물쇠"BOJ 2021. 11. 17. 22:43
# 문제 링크 https://www.acmicpc.net/problem/2478 2478번: 자물쇠 처음 k-왼쪽밀기의 k를 첫째 줄에, (p,q)-구간뒤집기의 p와 q를 빈칸을 사이에 두고 둘째 줄에, 그리고 마지막 k-왼쪽밀기의 k를 셋째 줄에 출력한다. 만일 답이 여럿일 경우에는 그 중 하나만 출력 www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 그리디 알고리즘이라고 생각한다. 위의 그림 1은 n이 4일때 가능한 구간 뒤집기의 결과 중 일부이다. 문제에서 제시한 순서에 따라 자물쇠를 만들어야 하므로 한 번 왼쪽밀기를 했을 때, 인접한 두 수의 차이는 1 혹은 n - 1이 됨을 알 수 있다. 따라서, 위와 같이 연속하거나, 차이가 n - 1이 되는 수열만이 가능하다는 것은 자명하다...
-
[Python 3] BOJ - 20530 "양분"BOJ 2021. 11. 14. 21:18
# 문제 링크 https://www.acmicpc.net/problem/20530 20530번: 양분 첫째 줄에 두 자연수 $N$, $Q$가 주어진다. 주어지는 그래프의 정점과 간선의 개수가 $N$개이며 쿼리가 $Q$개 주어진다는 것을 의미한다. 둘째 줄부터 $N$개의 줄에는 $i$번 간선이 연결하는 두 정점 www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 사이클 검출이라고 생각한다. 위 그림 1은 예제 입력 1의 경우를 나타낸 것이다. 이 때, 점선을 빼고 생각하면 이 그래프는 트리임이 자명하다. 트리의 성질로 인해 정점 수가 N개라면, 간선 수는 N-1개이다. 또한 문제에서 제시하는 두 조건, 중복 간선과 루프 간선이 없음을 트리는 만족한다. 그런데 문제에서는 입력으로 주어지는 그래..
-
[Python 3] BOJ - 16161 "가장 긴 증가하는 팰린드롬 부분수열"BOJ 2021. 11. 12. 13:49
# 문제 링크 https://www.acmicpc.net/problem/16161 16161번: 가장 긴 증가하는 팰린드롬 부분수열 팰린드롬 수열이란 앞에서부터 읽을 때와 뒤에서부터 읽을 때 똑같은 수열을 말한다. 수열 {13, 25, 3, 25, 13}, {9, 5, 5, 9}는 팰린드롬이고, {1, 2, 3, 4, 5, 6, 7, 6}, {1, 2, 5, 4, 2}, {1, 1, 3, 2, 4}는 팰린드 www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 투 포인터라고 생각한다. 위 그림 1은 문제에서 정의하는 증가하는 팰린드롬 수열의 예시인 [1,3,5,3,1]을 나타낸 그림이다. 그런데 위에서부터 2번째 그림인 [3,5,3]은 첫번째 수열의 부분수열임을 알 수 있고 [3,5,3] 역..
-
[Python 3] BOJ - 20191 "줄임말"BOJ 2021. 11. 6. 16:59
# 문제 링크 https://www.acmicpc.net/problem/20191 20191번: 줄임말 문자열 A가 문자열 B의 줄임말이라는 것은 B의 순서를 바꾸지 않고 0 또는 그 이상 개수의 문자를 지워 A를 만들 수 있다는 뜻이다. 정의에 의해서 B는 자기 자신의 줄임말임에 유의하라. 예를 들 www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 그리디 알고리즘과 이분 탐색이라고 생각한다. 위 그림 1은 t가 "aacba"인 경우를 나타낸 그림이다. 이 때 만일 s의 첫글자가 c인 경우를 생각해보자. 그렇다면, 두번째 글자는 a,b,c 중 하나일 것이다. 그런데 a와 b의 경우는 굳이 n을 증가시키지 않아도 얻을 수 있으나, c의 경우는 n을 증가시켜야만 얻을 수 있다. 따라서 현재 ..
-
[Python 3] BOJ - 13392 "방법을 출력하지 않는 숫자 맞추기"BOJ 2021. 11. 4. 20:10
# 문제 링크 https://www.acmicpc.net/problem/13392 13392번: 방법을 출력하지 않는 숫자 맞추기 아래 그림과 같이 N개의 회전이 가능한 숫자 나사가 아래위로 연결되어 있다. 가장 위에 있는 숫자나사는 숫자나사 1이고 가장 아래에 있는 숫자나사는 숫자나사 N이다. 모든 숫자나사는 각각 10 www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 다이나믹 프로그래밍이라고 생각한다. 상태 공간을 현재 idx번째 인덱스이고 위에서 부터 왼쪽으로 left번만큼 돌렸을 때 목표 숫자를 맞추기 위한 최소 움직임인 dp[idx][left]라고 정의하자. 자칫 상태 공간이 메모리 초과에 걸릴만큼 크다고 생각할 수 있으나, 위칸에서 왼쪽으로 얼마나 많이 돌릴지라도 10칸을 돌린..
-
[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인 경로는 큐의 앞에 넣음으로서 최대한 간선의 가중치가 작도록 움직이는 것이다. 문제에서 회사가 다른 두 정점은 환승이 필요하고, 두 정점 사이의 환승 횟수는 같은 ..