기록(記錄)

본문 바로가기

알고리즘

백준 문제 풀이 [Python] 7824번 Playing With Stones https://www.acmicpc.net/problem/7824 25/06/26 전형적인 스프라그-그런디 정리 문제이다. 플레티넘 200문제를 달성하기 위해 풀었던 문제들 중 하나이다. 문제 접근 방식: 문제가 영어로 되어 있기 때문에, 해석을 하자면 다음과 같다. 두 사람이 돌을 제거하는 게임을 함.$N$개의 돌 무더기가 주어져 있으며, 각각의 무더기에는 $a_1, a_2, \dots, a_n$개의 돌이 있음.자기 차례에 플레이어는 하나의 무더기에서 최소한 $1$개 이상의 돌을 제거해야하며, 해당 무더기의 돌 개수의 절반 이하만 제거할 수 있음.이때 돌을 제거할 수 있는 선택이 더 이상 없는 플레이어가 짐.두 사람이 최적으로 플레이 할 때, 선공이 이긴다면 "YES", 그렇지 않다면 "NO"를 출..
백준 문제 풀이 [Python] 31537번 출근하기 싫어 1 https://www.acmicpc.net/problem/31537 25/07/02 플레티넘 200문제를 채우기 위해서 풀만한 플레티넘 문제를 밀다가 푼 문제 중 하나이다. 간단한 조합론 문제이다. 문제 접근 방식: 문제를 요약하면 다음과 같다. 매 시간마다 최대 $1$명이 회사에 없어도 됨. 즉, 매 시간마다 확인했을 때 모든 사람이 있거나 한 사람만 빠져있어야 함. $M$시간을 확인하고, $N$명의 직원 각각 $M$시간 중 몇 시간동안 회사에 있었는지에 대한 정보가 $A_i$로 주어짐. 이때, $M$시간 동안 출근해 있는 직원들의 경우의 수를 구하는 것이 목적이다. $i$번째 직원은 $M$시간 중 $A_i$시간 나온다. 즉, $M$시간 중에서 $M-A_i$시간만큼 빠져있다. 최대 $1$명이 출근..
백준 문제 풀이 [Python] 11834번 홀짝 https://www.acmicpc.net/problem/11834 25/06/15 이전에 북마크 해두었던 문제로, 몇 개를 좀 나열해보다가 쉽게 해결할 수 있었다. 문제 접근 방식: 어떤 수열이 다음과 같은 규칙으로 주어진다. 홀수 $1$개, 짝수 $2$개, 홀수 $3$개, ... 이런 식으로 연속된 홀수와 짝수가 개수를 점점 늘려가며 늘어난다. 즉, $1 \ \ 2 \ 4 \ \ 5 \ 7 \ 9 \ \ 10 \ 12 \ 14 \ 16 \ \ \cdots$으로 이루어져있다. 이때 우리가 구하고자 하는 것은 이 수열의 $N$번째 항을 구하고 싶다. $N$의 제한이 $10^{100}$이므로, 당연히 시뮬레이션으로 구하면 터진다는 것을 확인할 수 있다. 따라서 우리는 $N$번째 항을 "이분 탐색"으로 ..

수학

회고록

감상록

티스토리툴바