🪄 돌 게임
마지막 돌을 가져가는 사람이 게임을 이길 때, 이기는 사람을 구하는 문제
게임 이론은 서로 최선을 다하므로 N의 값에 따라 선공, 후공중에서 누가 이기는지 정해져 있다.
(SK인 상근이가 먼저 시작하고, 돌을 1개 또는 3개를 가져갈 수 있음)
N = 1 → 상근이가 1개를 가져감 → SK 출력 (선공 승)
N = 2 → 상근이가 1개 가져감 → 창영이가 1개 가져감 → CY 출력 (후공 승)
N = 3 → 상근이가 3개를 가져감 → SK 출력 (선공 승)
→ 상근이가 1개를 가져감 → 2개가 남았을 때 돌을 가져가는 사람이 패배 → SK 출력 (선공 승)
N = 4 → 상근이가 1개를 가져감 → 3개가 남았을 때 돌을 가져가는 사람이 승리 → CY 출력
→ 상근이가 3개를 가져감 → 1개가 남았을 때 돌을 가져가는 사람이 승리 → CY 출력 (후공 승)
N = 5 → 상근이가 1개를 가져감 → N = 4일 때 후공이 승리 → SK 출력
→ 상근이가 3개를 가져감 → N = 2일 때 후공이 승리 → SK 출력 (선공 승)
N = 6 → 상근이가 1개를 가져감 → N = 5일 때 선공인 사람이 승리 → CY 출력
→ 상근이가 3개를 가져감 → N = 3일 때 선공인 사람이 승리 → CY 출력 (후공 승)
상근이가 1개를 가져감 → N = t - 1 일 때 선공이 승리 → CY 출력
상근이가 3개를 가져감 → N = t - 3 일 때 후공이 승리 → SK 출력
게임 이론은 서로가 최선을 다해서 플레이하기 때문에,
상근이는 자신이 이길 수 있는 최선의 플레이를 하기 때문에 돌을 3개 가져가서 SK를 출력한다.
n = int(input())
dp = [0] * (n + 1) # 1: 선공 승, 2: 후공 승
dp[1] = 1; dp[2] = 2; dp[3] = 1
for i in range(4, n+1):
if dp[i-1] == 2 or dp[i-3] == 2: dp[i] = 1
else: dp[i] = 2
if dp[n] == 1: print('SK')
else: print('CY')결국 N이 짝수일 때 창영이가 이기고 N이 홀수일 때 상근이가 이기기 때문에, 아래처럼 문제를 풀 수도 있다.
n = int(input())
if n % 2 == 0:
print('CY')
else:
print('SK')🪄 가장 긴 증가하는 부분 수열
어떤 수열이 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 문제
크기 N (1 ~ 1000)
수열 A = {10, 20, 10, 30, 20, 50}
시간복잡도는 O(N^2)이고, N은 최대 1,000이기 때문에 10^8 > 10^6 이므로 시간 내에 돌아간다.
n = int(input())
A = [*map(int, input().split())]
dp = [1] * n
for i in range(1, n):
for j in range(i):
if A[i] > A[j]: dp[i] = max(dp[i], dp[j] + 1)
print(max(dp))모든 경우의 수를 확인해보려면 A[i]에 값을 넣을 때,
A[0] ~ A[i-1]에서 가장 긴 부분 수열 + 1을 넣어주면 된다.
N = 100,000이 넘어간다면?
가장 긴 증가하는 부분 수열(2) 문제에서 N = 1,000,000 이므로 시간 초과!
→ bisect, bisect_left 사용
🪄 LCS
두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제
A = input()
B = input()
dp = [[0] * 1001 for _ in range(1001)]
ans = 0
for i in range(1, len(A) + 1):
for j in range(1, len(B) + 1):
if A[i-1] == B[j-1]: dp[i][j] = dp[i-1][j-1] + 1
else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
ans = max(ans, dp[i][j])
print(ans)