[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$까지의 모든 수가 최소 하나씩 있고 $..
[Python] 12850번 본대 산책2
https://www.acmicpc.net/problem/12850 23/03/21 예전에 이 문제에 대한 풀이 글을 작성한 것 같았는데, 지금 검색해보니 작성하지 않아서 오랜만에 작성하려고 한다. 그래프를 인접 행렬로 나타낼 수 있는지에 대한 지식과, 그 행렬을 거듭제곱하면 경로의 개수가 나온다는 지식을 요구하는 문제다. 문제 접근 방식: 본대 산책1이 있고 본대 산책2가 있는데, 둘은 제한만 다른 문제다. 본대 산책2는 본대 산책1에 분할 정복을 이용한 거듭제곱 태그가 들어가서 난이도가 더 뛰어버렸다. (사실 그 정도로 어려운가 싶지만, 그렇다고 하자.) 문제에서 주어진 그래프를 인접 행렬의 형태로 바꿔보자.matrix = [[0, 1, 1, 0, 0, 0, 0, 0], [1, ..
