글 (385) 썸네일형 리스트형 [MatKor] Math is difficult 문제 수학을 좋아하는 하늘이는 수학을 싫어하는 재우에게 문제를 냈다. $i \in \mathbb{N}$과 $\alpha , \beta \in \mathbb{N}$에 대하여 $0 < a_i < a_{i+1}$와 $\alpha a_i < a_{i+2}$, 그리고 $a_{i+2} \equiv \alpha a_i (\mathrm{mod} \ \beta a_{i+1})$, $a_i \in \mathbb{N}$을 만족하는 수열 $\{ a_i \}$가 있다. 이때 자연수 $N$이 주어질 때, 위의 조건을 만족하는 수열 중 $a_N$을 최소로 만드는 수열을 $f(N) = \{ a_1, a_2, \cdots , a_N \} $라고하자. 또한, 이러한 $f(N)$에 대하여 원소의 합을 $S(N) = \sum_{i = 1}.. [Python] 9718번 Matrix Transformation https://www.acmicpc.net/problem/9718 9718번: Matrix Transformation The first input line contains a positive integer,n, indicating the number of matrices (test cases). Each matrix starts with a line containing R(2≤R≤30) and C(2≤C≤30) separated by a single space. Each of the next R lines contains C integers. Each of www.acmicpc.net 23/03/14 불변량의 개념을 숙지한 상태라면 쉽게 접근할 수 있는 문제이다. 만약 이 문제를 크기 제한($2 \leq.. [Python] 2758번 로또 https://www.acmicpc.net/problem/2758 2758번: 로또 선영이는 매주 엄청난 돈을 로또에 투자한다. 선영이가 하는 로또는 1부터 m까지 숫자 중에 n개의 수를 고르는 로또이다. 이렇게 열심히 로또를 하는데, 아직까지 한 번도 당첨되지 않은 이유는 www.acmicpc.net 23/03/13 전형적인 2차원 DP문제로, 만약 DP가 아니라 백트래킹으로 접근한다면 시간초과가 날 수도 있을 문제이다. 문제 접근 방식: $\mathrm{DP}$문제를 접근할 때에는 먼저 상태를 정의하는게 우선이다. 이 문제에서는 영향을 미치는 요소가 $n$과 $m$ 두가지 라는 사실을 알 수 있다. 때문에 다음과 같이 상태를 정의해보자. $\mathrm{DP}[i][j]$ $=$ 선영이가 지금까지 $.. [Python] 1563번 개근상 https://www.acmicpc.net/problem/1563 1563번: 개근상 백준중학교에서는 학기가 끝날 무렵에 출결사항을 보고 개근상을 줄 것인지 말 것인지 결정한다. 이 학교는 이상해서 학생들이 학교를 너무 자주 빠지기 때문에, 개근상을 주는 조건이 조금 독 www.acmicpc.net 23/03/09 3차원 DP문제로, 상태를 정의하기만 하면 점화식을 구성하는 것은 그렇게 어렵지 않아서, 쉽게 풀 수 있는 문제이다. 문제 접근 방식: 문제를 자세히 보면, 개근상을 받을 수 없는 경우를 주목해야 할 필요가 있다. 개근상을 받을 수 없는 경우는 $N$일 중에서 지각이 $2$회 이상이거나, 결석이 연속 $3$회 이상이면 개근상을 받을 수 없다. 반대로 말하면, $N$일 중에서 지각이 $1$회 이.. [Python] 1229번 육각수 https://www.acmicpc.net/problem/1229 1229번: 육각수 육각수는 육각형을 이용해 정의할 수 있다. hn은 한 변에 점 1, 2, ..., n개가 있는 육각형을 점 하나만 겹치게 그렸을 때 존재하는 서로 다른 점의 개수이다. 그림 1 그림1은 h1, h2, h3, h4를 의미하며, www.acmicpc.net 23/03/09 조금은 독특한 방식의 DP문제로, 문제에서 주어진 정보를 적극 활용하여 미리 전처리를 해 시간을 대폭 줄여야 하는 문제이다. 만약 문제에서 주어진 정보가 없었더라면 조금은 더 까다로웠을 지 모른다. 이전에 도전했다가 시간초과를 여러 번 받아 실패했던 문제로, 이 글을 통해 도움을 받았으면 좋겠다. 문제 접근 방식: 이 문제는 캡틴 이다솜 문제와 유사한 방.. [Python] 2421번 저금통 https://www.acmicpc.net/problem/2421 2421번: 저금통 홍태석은 저금통 2개를 가지고 있다. 홍태석은 매일매일 하나의 저금통에 1원을 넣는다. 두 저금통에 모두 N원이 모이면 태석이는 새로운 장난감을 살 수 있기 때문에, 저금을 멈춘다. 홍태석은 www.acmicpc.net 23/03/12 전형적인 2차원 DP문제로, 현재 상태를 잘 정의하고 점화식을 세우면 쉽게 해결할 수 있다. 문제 접근 방식: 문제를 보고 처음에 발견한 사실은, 첫번째 저금통에 돈을 넣거나 두번째 저금통에 돈을 넣거나 둘 중 하나의 상태로만 갈 수 있다는 사실을 알아냈다. 이를 통해 $\mathrm{DP}[i][j]$ $=$ 첫번째 저금통에 $i$원을 넣고, 두번째 저금통에 $j$원을 넣었을 때, 소수.. [Python] 22770번 Ellipse Intersection https://www.acmicpc.net/problem/22770 22770번: Ellipse Intersection Input may contain multiple test cases. The first line is a positive integer n (n ≤ 100), denoting the number of test cases below. Each case is composed of two lines, the first one is the description of orbit A, and the second one the description of orbit www.acmicpc.net 22/12/31 전형적인 수학문제로, 극좌표로 적분을 해야하는 문제이다. 극좌표 적분에 관한 내용은 미적분학.. [정수론] 1-1. Numbers and Sequences $\S$ Well-Ordering Property (WOP / 정렬 원리)란? 모든 공집합이 아닌 자연수 집합 $\mathbb{N}$의 부분 집합 $S$는 최소 원소(min element)가 존재한다. ( $\forall$ $S \subset \mathbb{N}$ and $S \neq \varnothing$, $S$ has min element.) 정수론에서는 이를 공리로써 받아들인다. 이를 넓혀, 임의의 어떤 집합 $R$의 모든 공집합이 아닌 부분 집합 $S$가 항상 최소 원소를 가지고 있다면, 우리는 이 집합 $R$이 "Well-Ordered"돼있다고 이야기한다. 예를 들어 보자. $\mathbb{N}$은 Well-Ordered 이다. $\mathbb{Z}$는 not Well-Ordered 이다. 그.. 이전 1 ··· 26 27 28 29 30 31 32 ··· 49 다음
