게임이론2 [Python] 백준 16884 나이트 게임 문제 링크 : https://www.acmicpc.net/problem/16884 1. 접근 방법 모든 경우의 수를 탐색하기에는 너무 경우의 수가 많았다. 최대 10,000이지만, n일 때 결과가 n + 1일 때 결과 및 과정에 직접적인 인과 과정을 찾을 수 없었기 때문에, DP 식의 풀이 과정은 옳지 않다고 생각했다. 만약 각각 과정을 백트레킹으로 계산할 수도 있지만, 최대 100개의 테스트 케이스가 주어지면 불가능할 것이라 생각했다. 2. 풀이 코드 🖥python 코드 : https://github.com/mintropy/baekjoon_py/blob/master/16000/16884.py GitHub - mintropy/baekjoon_py Contribute to mintropy/baekjoon_.. 2021. 11. 6. [Python] 백준 16888 루트 게임 문제 링크 : https://www.acmicpc.net/problem/16888 16888번: 루트 게임 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 105)가 주어진다. 둘째 줄부터 T개의 줄에 테스트 케이스가 한 줄에 하나씩 주어지며, N(1 ≤ N ≤ 106)이 주어진다. www.acmicpc.net 1. 접근 방법 소수 판정 에라토스테네스 체와 비슷한 방식으로 해결될 것이라 생각이 들었다. 처음에는 각 조건마다 다음 턴을 거꾸로 탐색하는 과정을 반복했는데, 시간이 생각보다 많이 걸려서, 에라토스테네스 체에서도 사용하는 아이디어인, 소수를 발견하면 배수를 모두 소수가 아님을 표시하는 방법을 채용하여 해결했다. 2. 풀이 코드 🖥python코드 import sys input = sys.stdi.. 2021. 10. 28. 이전 1 다음