본문 바로가기

Computer Science/PS37

[백준 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.
[백준 5615] 아파트 임대 (Feat. 밀러-라빈 소수 판정법) (Platinum I) https://www.acmicpc.net/problem/5615 5615번: 아파트 임대 첫째 줄에 아파트의 면적의 수 N이 주어진다. 다음 줄부터 N개 줄에 카탈로그에 적혀있는 순서대로 면적이 주어진다. N은 100,000이하이고 면적은 231-1이하인 양의 정수이다. www.acmicpc.net 매우 자명한 어떤 절차에 의해, 2N + 1이 소수가 되는 N을 찾는 문제임을 알 수 있다. Naive한 소수 판별을 짜면 시간복잡도 \(O(T \sqrt{N})\)이 나와서 TLE가 난다. 시간복잡도를 줄일 수 있는 방법으로 밀러-라빈 소수 판정법을 이용하자. a = 2, 7, 61에 대하여 \( n - 1 = 2^s d \)로 놓는다. \( a^d \ne 1 \mod n \)이고, 모든 r : 0 ~ s.. 2022. 8. 28.
[백준 9206] 나무 말고 꽃 (Platinum II) https://www.acmicpc.net/problem/9206 9206번: 나무 말고 꽃 선영이와 남자친구의 2주년이 얼마 남지 않았다. 선영이는 그를 위해 특별한 것을 사주려고 한다. 남자친구는 나무에 관심이 매우 많다. 하지만, 선영이는 나무는 선물로 매우 크다고 생각한다. www.acmicpc.net 수치해석 문제들이 다 그렇듯이 수많은 시도를 해야 풀 수 있다... 일단 constexpr로 각종 상수를 정의해 주자. constexpr value들은 컴파일 시점에 평가되기 때문에, #define 같은 매크로의 기능을 거의 모두 쓸 수 있으면서 그것보다 더 안전하다고 할 수 있겠다. constexpr long double PI = 3.1415926535897932384626l; constexpr .. 2022. 8. 26.
[백준 18222] 투에-모스 문자열 (Silver II) 5줄 안으로 구현하기 https://www.acmicpc.net/problem/18222 18222번: 투에-모스 문자열 0과 1로 이루어진 길이가 무한한 문자열 X가 있다. 이 문자열은 다음과 같은 과정으로 만들어진다. X는 맨 처음에 "0"으로 시작한다. X에서 0을 1로, 1을 0으로 뒤바꾼 문자열 X'을 만든다. X의 뒤에 www.acmicpc.net 문제에서는 숫자를 1부터 세지만 우리는 편의상 숫자를 0부터 세도록 하자. 임의의 자연수 n에 대해, n의 2진수 표현에서 비트 값을 (아무 위치에서나) 1만큼 바꿔 준 수 m을 고려하자. 그러면 n번째 투에-모스 문자열과 m번째 투에-모스 문자열 값은 그 parity가 반대임을 알 수 있다. 따라서 n의 2진수 표현의 비트 수를 세 준 뒤 2로 나눈 나머지를 출력하기만.. 2022. 8. 20.
[백준 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.
[백준 1168] 요세푸스 문제 2 (Platinum III) (Feat. PBDS) - 세그먼트 트리 없이 풀기 https://www.acmicpc.net/problem/1168 1168번: 요세푸스 문제 2 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 100,000) www.acmicpc.net 컴퓨터공학과에서 를 수강한 학생들이라면 std::set이 레드-블랙 트리로 구현되어 있다는 것을 알 것이다. 레드-블랙 트리는 Binary Search Tree다. 즉 원소들이 나름의 순서를 갖추고 정렬되어 있다는 것이다. 정렬되어 있다는 것은, 마치 Binary Search 하듯이 k번째 원소를 O(logn) 안에 접근할 수 있음을 함의한다. 그러나 그것을 하기 위해서는 rb-tree의 각 노드들이 subtree의 개수를 저장하고 있어야 한다. std::set은 이 기능을 제공하.. 2022. 8. 17.
[백준 18542] Permutant (Ruby III) 풀이 https://www.acmicpc.net/problem/18542 18542번: Permutant Consider an \(n \times n\) matrix \(A\). Let us denote element in \(i\)-th row and \(j\)-th column as \(A_j^{(i)}\). You are given a sequence \(a_1, \dots , a_n\) and a permutation \(π_1, \dots , π_n\) such that the first row is formed by sequence \(a_k www.acmicpc.net 먼저 주어진 Permutation는 Linear Transform의 일종임을 파악해야 한다. 예를 들어, Permutation {.. 2022. 8. 4.