[백준 25384] 니은숲 예술가 (Diamond V)
https://www.acmicpc.net/problem/25384 25384번: 니은숲 예술가 만들 수 있는 조형물의 가짓수를 $998\, 244\, 353$$(=119\times 2^{23}+1)$으로 나눈 나머지를 출력한다. $998\, 244\, 353$은 소수이다. www.acmicpc.net 조형물의 상태로 가능한 것을 아무거나 하나 그려 보았다. 그림과 같이, 네 면 중 인접한 두 면에는 가장 마지막 조각만이 있고, 나머지 두 면에는 연속된 여러 개의 조각들이 나타난다. 따라서 부분 문제를 다음과 같이 정의할 수 있겠다. - \( DP(n, i, j) \) : 네 면 중 두 면에 n번째 조각이 나타나고, 한 면에 i~n번째 조각이, 한 면에 j~n번째 조각이 나타남. n = 4, (조각) =..
2022. 8. 31.
[대학생 수학경시대회] 2019년 제2분야 7번
7. 벡터 \( v_1, v_2, v_3, v_4 \)는 길이가 각각 2, 3, 4, 5이며 서로 수직이다. 임의의 2차원 부분공간 \( W \subset \mathbb{R}^4 \)에 대하여 \( v_1, v_2, v_3, v_4 \)를 \( W \)에 정사영하여 얻은 벡터들 가운데 적어도 하나는 길이가 1이 아님을 보여라. Sol) 일반성을 잃지 않고 \( v_1 = 2e_1, v_2 = 3e_2, v_3 = 4e_3, v_4 = 5e_4 \)라 하자. 그리고 선형사상 T를 Tv = (v의 W 위로의 정사영)으로 잡는다. 이제 네 정사영의 길이가 모두 1이라 가정하면 $$ \left\langle e_1, Te_1 \right\rangle = {1 \over 4}, \left\langle e_2, Te..
2022. 8. 28.
[백준 25323] 수 정렬하기, 근데 이제 제곱수를 곁들인 [UCPC 2022 예선] (Platinum V)
https://www.acmicpc.net/problem/25323 25323번: 수 정렬하기, 근데 이제 제곱수를 곁들인 양의 정수로 이루어진 길이가 $N$ 인 수열 $A_1,A_2,\cdots ,A_N$이 존재할 때, 다음 행동을 원하는 만큼 반복할 수 있다. $1\leq i,j\leq N;i\neq j$이면서 $A_i\times A_j$가 제곱수인 $i$, $j$를 선택해, $A_i$와 $A_j$ www.acmicpc.net AB가 제곱수이고, AC가 제곱수이면 BC도 제곱수이다. 증명 : (A^2)BC가 제곱수고, 제곱수를 제곱수로 나누면 제곱수라는 사실로부터 자명하다. 반대로 AB가 제곱수이고, AC가 제곱수가 아니면, BC도 제곱수가 아니다. (증명은 위와 똑같이 하면 된다) -> 수열이 몇 ..
2022. 8. 20.
