https://www.acmicpc.net/problem/9660 9660번: 돌 게임 6 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1,000,000,000,000) www.acmicpc.net 백준에는 돌 게임이 참 많다. 이 문제는 solved.ac 기준으로 골드5의 난이도를 가지고 있는데 실버에 속한 돌 게임과의 차이점은 N의 범위가 굉장히 크다는 것이다. 따라서 O(N)의 풀이조차도 TLE가 발생한다. 이런 게임이론 같은 경우에는 규칙을 찾아 푸는 것이 가장 편한 방법인 듯하다. 못찾으면 난이도가 급상승하니.. 수학적으로 머리가 비상해서 규칙만 읽고 규칙을 찾을수만 있다면 정말 좋겠지만 필자는 똑똑이가 아니라서 적당한 탐색을 통해 규칙을 찾기로 했다. 우선 돌이 1~4개 있을 때를 생각해보자. ..

https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부� www.acmicpc.net 작업의 우선순위가 주어지고 특정 작업을 수행하기 위해서는 그 작업보다 먼저 수행되어야하는 작업들이 모두 완료되어야한다. 이 문제와 마찬가지로 위상 정렬 문제라는 것을 알 수 있다. 하지만 이 문제는 특정 건물을 지을 수 있는 시간을 묻는 것이므로 단순 위상정렬 뿐만이 아닌 구현이 필요하다. 이 그림을 확인해 보자. 건물 1의 경우 10초가 소요 될 것이다. 건물 2와 3의 경우에는 각각 1..

https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net N의 제한이 10이다. 바로 백트래킹이 아닐까? 라는 추측을 할 수 있다. https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 또한 이 문제와 비슷한 문제라는 것 ..

https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 작업들의 순서가 주어지고 후에 이루어지는 작업들은 앞에 이루어지는 작업들이 모두 완료되어야만 가능한 문제들은 위상 정렬(topological sort) 로 해결할 수 있다. 이 문제 또한 단순한 위상 정렬 문제로 보이지만 3번 조건을 보면 가능한 쉬운 문제부터 풀어야한다. 라고 명시되어있다. 문제의 난이도는 문제의 번호이므로 수행할 수 있는 문제 중 가장 낮은 번호의..

https://www.acmicpc.net/problem/1238 1238번: 파티 문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 www.acmicpc.net 단방향 그래프가 주어졌을 때 도착점까지 왔다가 돌아올 수 있는 최단 거리중 최댓값을 구하는 문제. 다익스트라 알고리즘을 이용하여 각 정점들에 대해 도착점 -> 정점들의 거리를 일단 구해준다. 그 후에 각 정점들에 대해 다익스트라 알고리즘을 사용하여 정점 -> 도착점까지의 거리를 구한 뒤 앞에서 구한 도착점 -> 정점 까지의 거리를 더해준 것들 중 최댓값을 구해주면 된다. 아래는 소스코드이다...

A. Matrix Game (1100) n x m 크기의 행렬이 주어졌을 때 각 칸마다 0은 unclaimed, 1은 claimed 칸을 나타내며 unclaimed 한 칸을 claimed 하기 위해서는 그 칸의 행과 열에 claimed 칸이 존재하지 않아야한다. 이 때 Ashish와 Vivek이 Ashish가 먼저 claim을 시작 할 때 어떤 칸도 claimed 할 수 없게 되었을 경우 패배한다. 두 플레이어가 최적의 선택을 번갈아가며 했을 때 누가 승리하는지 출력하는 문제였다. A번부터 게임이론이 나왔다. 우선 쉽게 관찰할 수 있는 부분은 claim 가능한 칸의 갯수가 홀수면 Ashish가 승리하며 짝수면 Vivek이 승리한다는 것. 따라서 우리는 모든 칸에 대해 그 칸의 행과 열 중 1이 존재하는지..

https://www.acmicpc.net/problem/5397 5397번: 키로거 문제 창영이는 강산이의 비밀번호를 훔치기 위해서 강산이가 사용하는 컴퓨터에 키로거를 설치했다. 며칠을 기다린 끝에 창영이는 강산이가 비밀번호 창에 입력하는 글자를 얻어냈다. 키로거� www.acmicpc.net C++의 STL list를 이용하여 해결 가능한 문제이다. iterator를 이용해 해결하자. 아래는 소스코드이다. 더보기 #include #define endl '\n' #define pb push_back #define mp make_pair #define MOD 998244353 #define cont continue #define rep(i, n) for(int i = 0 ; i < (n) ; i++) u..