본문 바로가기

파이썬

 (320)
[Python] 1520번 내리막 길 https://www.acmicpc.net/problem/1520 24/11/13  무난한 DP이다. 처음에는 바텀업으로 생각했으나, 잘 생각나지 않아서 탑다운으로 짰다. 문제 접근 방식:  DP식을 다음과 같이 정의하자. DP[i][j] = $(i, j)$번째 칸에 왔을 때 항상 내리막 길로만 오는 경우의 수. 우리의 목적은 $DP[N-1][M-1]$의 값을 구하는 것이다. 또한, $DP[0][0] = 1$임을 알고 있다. 내리막 길로 간다는 것은 현재 칸보다 이전의 칸에 쓰여있는 숫자가 더 크다는 뜻이다. 따라서, 기본적으로 현재 칸을 둘러싸고 있는 4개의 주변 칸, 즉, 이전의 칸에 쓰여있는 숫자가 더 크다면, 그 칸을 통해 현재 칸으로 올 수 있다. 따라서, 4개의 주변 칸에 대해서 DP값을 찾아..
[Python] 32645번 동까뚱뽭 게임 https://www.acmicpc.net/problem/32645 24/11/11  간단한 게임이론 + 트리 DP문제이다. 문제 접근 방식:  DP상태 식을 다음과 같이 정의해보자. DP[i] = $i$번째 노드에서 게임을 진행할 때 누가 이기는 지에 대한 여부 DP[i] = 0이라면 후공이 이긴다고 하고, 1이라면 선공이 이긴다고 하자. 뭐, 게임이론 많이 한 사람들이라면 스프라그-그런디로 생각해서 mex때릴 수도 있는데, 사실 게임이 하나 뿐이라서 선후공 승패 여부만 따지면 되기 때문에 간단한 게임 DP로도 풀린다. $i$번째 노드에서 밑으로 갈 수 있는 노드를 below라고 한다면, DP[below]가 모두 1이라면, 즉, 선공이 이기는 노드라면 현재 노드는 후공이 이기는 노드(즉, 선공이 지는 ..
[Python] 32299번 게임을 만들어요 https://www.acmicpc.net/problem/32299 24/11/10  전형적인 게임이론 문제다. 문제 접근 방식:  $N=3$인 경우를 제외하면 항상 후공이 이긴다. 그 이유는 게임 판을 도넛 모양으로 분리하면, 한 도넛에서 다른 도넛으로 움직일 때마다 선공과 후공의 유리한 정도가 달라지는데, 다른 도넛으로 움직일 때 후공이 유리하다면 후공은 그냥 그 방향으로 움직이면 되고, 다른 도넛으로 움직일 때 선공이 유리하다면, 후공이 현재 도넛에서 빙빙 돌면서 선공이 다른 도넛으로 넘어가도록 만들 수 있기 때문이다. 게임이론에서 자주 나오는 테크닉인데, 핵심은 후공이 항상 선공이 불리하도록 게임판을 "조정"할 수 있다는 것이 핵심이다. 아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다...
[Python] 4354번 문자열 제곱 https://www.acmicpc.net/problem/4354 24/09/26  KMP로 유명한 문제다. 근데 이 문제는 KMP로 안풀어도 된다. 사실 이 방법이 더 쉽다. 문제 접근 방식:  엥 그러면 어떻게 접근하는 거야, 라고 생각하겠지만, 그냥 나이브하게 풀린다. 문자열의 길이를 $N$이라고 하면, $N$의 약수가 반복되는 문자열의 길이가 될 수 있다. 따라서 $N$의 약수 $i$에 대해서, 기존 문자열 $S$를 슬라이싱한 부분 문자열, $S[:i]$가 $S$에서 몇 번 반복되는지 count함수를 통해 확인한다. 그 반복 횟수*부분문자열의 길이가 원래 문자열의 길이 $N$이 된다면 바로 종료하면 된다.(가장 짧은 부분 문자열을 찾는 것이므로) 그렇다면 이게 왜 되는지 궁금할텐데, 파이썬에서 s..
[Python] 32518번 대충 블록에서 영혼 탈출시키는 게임 https://www.acmicpc.net/problem/32518 24/11/08  간단한 탑다운 DP다. 바텀업으로는 해결할 수 없다. 문제 접근 방식:  처음에는 $N$의 제한이 $10^{18}$인 것을 보고 DP가 아니라 하나의 완성된 수식으로 나올 줄 알고 100까지의 바텀업 DP를 돌렸다. 뚜렷한 규칙이 보이지 않아서, 수학적으로 해결하는 것은 그만두고, 다른 해결방법이 있는지 모색하기 위해 어떤 경우에 최댓값이 나오고, 그때 분할되는 경우가 어떤 경우인지를 모두 찾는 코드를 작성했다. $N-2$가 3으로 나눠진다면, $((N-2)//3, (N-2)//3, (N-2)//3)$과 같이 분할된다.  예를 들어, 8과 같은 경우, 들어내는 블록을 기준으로 3개의 체인이 나오는데, 각 체인의 길이는 ..
[Python] 32387번 충전하기 https://www.acmicpc.net/problem/32387 24/10/06   KCPC 당시, 파이썬으로 검수했던 문제다. 다양한 풀이가 있어서 나름 연습해보기 적절한 문제라고 생각한다. 문제 접근 방식:  문제의 요구 사항은 다음과 같다. 크기가 $N$인 Bool 배열 $A$가 주어지고, 두 종류의 쿼리가 주어진다. 쿼리의 개수는 최대 $10^6$개이며, 배열의 최대 크기는 $10^6$이다. 또한, 배열의 초기 상태는 모두 False로 초기화되어있는 상황이다. 1번 쿼리는 인덱스 $i$가 주어진다. $i$보다 크거나 같은 인덱스 $k$중에서, $A[k]$ = False로 되어있는 가장 작은 인덱스를 True로 바꾸는 것이다. 만약 이것이 불가능하다면 $-1$을 출력한다. 2번 쿼리는 인덱스 $..
[Python] 32228번 등차수열 만들기 https://www.acmicpc.net/problem/32228 24/09/15  맷코컵 당시 검수했던 문제 중 하나이다. 알면 보자마자 떠오르는 낚시 문제다. 문제 접근 방식:  문제에서는 주저리 주저리 적혀져 있는데, 오일러 파이 함수의 값을 출력하면 끝이다. 그러면, 결론이 왜 그렇게 나오는지에 대해 알아야 한다. 문제에서 주어진 것 처럼 mod $M$에서의 등차수열을 직접 구하는 방식으로 $K$값을 짜내려고 한다면 곤란하다. $N$의 제한과 $M$의 제한이 꽤나 크기 때문이다. $A_i$와 $M$이 서로소라는 조건, 모두 같은 $K$제곱을 하여 $A_{i}^{K}$로 만들고 mod $M$과 엮는다는 점을 유의깊게 생각하면 쉽게 파악할 수 있다. 이 $K$의 값이 $\varphi (M)$이 된다..
[Python] 32229번 B끼B끼 A끼A끼 수열 찾기 https://www.acmicpc.net/problem/32229 24/09/14  맷코컵 때 검수했던 문제 중 하나이다. 지문을 해석하는 재미가 있는 문제다. 그것과는 별개로, 제목이 별로다. 문제 접근 방식:  일단, 문제 해석을 하면 이 문제의 80%는 해결한 것과 다름이 없다.  먼저, 집합 $S$의 정의를 유의 깊게 보자. 문제에서 주어지는 입력은 $A, B, N$이다. $S$는 순서쌍 $(x, y)$들의 모임인데, 작은 것이 $x$이고 큰 것이 $y$이다.($x  또한, 이 둘의 차이는 $A$또는 $B$이며, $x$는 최소 $1$, $y$는 최대 $N$의 값을 가질 수 있다.  이제 수열 $P$의 정의를 유의 깊게 보자. 수열 $P$에는 $1$부터 $N$까지의 모든 수가 최소 하나씩 있고 $..

티스토리툴바