왕도를 찾아서

https://www.acmicpc.net/problem/13018 13018번: 특이한 수열 첫째 줄에 n, k (1 ≤ n ≤ 105, 0 ≤ k ≤ n)가 주어진다. www.acmicpc.net 골드3 난이도의 수학 분류 문제다. 이 문제의 핵심은 바로 임의의 자연수 N에 대해 N과 N+1은 서로소라는 것에 있다. i와 A[i]가 서로소가 아닌 게 k개로 서로소인 게 n-k인 것이다. 이 때 n-k를 p라고 하자. 1은 모든 수랑 서로소이기도 하다. 그러면 숫자를 이런식으로 1씩 밀려 쓰면 1 2 3 4 5 2 3 4 5 1 이러면 모든 i에 대해 A[i]와 i가 서로소가 된다. 1부터 p까지 모든 수에 대해서만 이렇게 밀려 쓰면 된다. 그 뒤 모든 수들은 밀려쓰지 않고 그대로 쓰면 된다. 이를테면..

https://www.acmicpc.net/problem/23325 23325번: 마법천자문 최근最近 만화漫畫 마법천자문魔法千字文을 감명感銘 깊게 읽은 연두然斗는, 모든 수數를 한자漢字로 적기 시작始作했다. 그런데 수업授業을 들으면서 필기筆記 해놓은 내용內容을 복습復習 www.acmicpc.net 전형적인 DP문제다. 요즘 너무 DP만 푸는거 같긴 하다. 계단 문제랑 비슷한 원리다. https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문자열 s의 0번째부터 i..

https://www.acmicpc.net/problem/15011 15011번: Irrational Division Your family has been blessed with chocolate! A huge piece of chocolate has been given to you and your sister to share. However, as you gobbled up the large majority last time, your parents have invented a game to keep things fair (and to keep you occupied www.acmicpc.net 설명은 귀찮으니 그냥 코드로 대체...... 입력이 최대 100이라서 시간복잡도가 아주 널널한 편이다. 내가..

https://www.acmicpc.net/problem/4342 4342번: 유클리드 게임 유클리드 게임은 두 명이서 하는 게임이고, 자연수 2개로 시작한다. 동혁이와 동규는 유클리드 게임을 하려고 한다. 동혁이가 먼저 시작한다. 동혁이는 큰 수를 작은 수의 배수만큼 뺀다. 이때, www.acmicpc.net 골드2 게임이론 문제 치고는 발상이 좀 쉬운 편이다. 내 차례에 숫자가 X X 2*X X 3*X X 등등등 큰 수가 작은 수의 배수라면 무조건 내가 이긴다. 그럼 큰 수가 작은 수의 배수가 아닌 경우라면? 큰 수를 big, 작은 수를 sma라고 부르자. big=sma+1이면 (sma>1) 내 차례에 내가 할 수 있는 건 딱 한가지다. 그리고 상대 차례에 sma 1 이렇게 두 숫자가 주어질 거다. ..

https://www.acmicpc.net/problem/11565 11565번: 바이너리 게임 첫 번째 줄에는 문자열 a, 두 번째 줄에는 문자열 b가 주어진다. 두 문자열은 0과 1로만 이루어져 있으며, 문자열 a와 문자열 b의 길이는 1 이상 1,000 이하이다. www.acmicpc.net 문자열 a에서 1의 개수를 ca라고 하고 문자열 b에서 1의 개수를 cb라고 하자. ca가 홀수인 경우 parity(a)가 1이기 때문에 문자열 끝에 1을 추가할 수 있다. 그러면 parity(a)가 0이 된다. 이러면 문자열 끝에 0을 맘껏 추가할 수 있다. 문자열 앞에서부터 1을 지울 때까지 숫자를 계속 지우면 parity(a)가 1이 된다. 그러면 또 문자열 끝에 1을 추가할 수 있다. 다만, 어떻게 해도..

https://www.acmicpc.net/problem/3015 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net 플래티넘 입문하기 좋은 문제다. 비슷한 느낌의 문제로 탑이 있다. https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.n..

백준 상위 100문제에서 실버가 사라졌다.

https://www.acmicpc.net/problem/3358 3358번: Towers of coins Asen and Boyan are playing the following game. They choose two different positive integers K and L, and start the game with a tower of N coins. Asen always plays first, Boyan – second, after that – Asen again, then Boyan, and so on. The boy in turn can www.acmicpc.net 게임이론 문제이면서 DP로 푸는 문제다... 사실상 돌 게임 6이랑 똑같은 문제다. https://www.acmicpc.ne..

https://www.acmicpc.net/problem/16888 16888번: 루트 게임 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 105)가 주어진다. 둘째 줄부터 T개의 줄에 테스트 케이스가 한 줄에 하나씩 주어지며, N(1 ≤ N ≤ 106)이 주어진다. www.acmicpc.net 게임 이론 문제는 DP로 풀어야 하는 게 있고 규칙성을 찾아야 하는 게 있는데 이건 DP로 푸는 문제다. STEP 0. bool dp[] 배열을 생각해보자 dp[i]에는 내 차례에 숫자가 i일때 내가 이기면 true, 내가 지면 false값을 저장한다. 그럼 일단 dp[1]=1, dp[4]=1, dp[9]=1, ...... 모든 제곱수 i에 대해 dp[i]=1이다. STEP 1. i가 제곱수가 아니라면 i 이..

https://www.acmicpc.net/problem/24678 24678번: 돌무더기 게임 1 첫 번째 케이스에서 R의 첫 시행 이후 가능한 다음 상태는 $(0,0,2), (0,2,0), (2,0,0)$뿐이며, B는 더 이상 시행을 할 수 없으므로 이긴다. 두 번째 케이스에서 R의 첫 시행 이후 가능한 다음 상태는 다음 www.acmicpc.net 풀이를 한 100줄 쓴 거 같은데... 쓰다가 다 지워버렸다. 너무 간단한 풀이가 생각나서 돌무더기가 내 차례에 짝수 짝수 짝수 상태로 놓여있다고 생각해보자 그럼 상대편 차례일때는 무조건 홀수 홀수 홀수 일 것이다. 왜냐하면 각 돌무더기에 대해 돌 하나를 가져가거나 올려놓거나 하니까 짝수는 홀수로 홀수는 짝수로 바꾸는 거다. 그리고 내 차례엔 무조건 짝수..