본문 바로가기

전체 글

 (113)
골드 이상 풀이 정리 2주차 1. 숫자 연결하기 (BOJ 1323)pigeonhole principle 언제 한번 순환소수 구할 때 나눗셈을 해본 적이 있다면 좋은 아이디어를 떠올릴 수 있다.1. 수를 계속 추가하면서(순환소수라면 0이었고, 이 문제에서는 N이다.) K로 나눠서 나머지를 알아낸다. 그후 그 나머지+N(여기선 문자열 연산이라 생각)을 다시 합쳐서 K로 나눈다.2. 계속 하다보면 언젠가 반복되었다.즉, 예제를 생각해보면 2%9=2 -> 22%9 -> 42%9 -> 62%9 -> ... 이런 식으로 계속 연산해준다. K로 나눈 나머지는 반드시 0~K-1이므로 비둘기집 원리에 따라 최대 K번 안에 반복된다. 같은 나머지가 나왔는데도 나머지가 0으로 안 나온다면 영원히 못 나누므로 -1을 출력하고 아니면 횟수를 출력하면 된다..
골드 이상 풀이 정리 1주차 1. 동전 (BOJ 9084)dp, knapsack 동전 하나를 잡고 그 동전의 값 이상부터 n까지 이전 값을 불러오면 된다. 당연히 0원은 무조건 만들 수 있으니 1로 초기화 해서 시작하면 된다. 2. 겹치는 선분 (BOJ 1689)sweeping, sorting imos법 같이 돌리면 된다. 즉, 시작 점은 1로 두고, 끝 점은 -1로 둬서 점의 위치를 중심으로 정렬해준다.예를 들어 (1, 5), (3, 6), (2, 3)가 있으면 (1, 1), (2, 1), (3, -1), (3, 1), (5, -1), (6, -1)로 될 것이다. 그리고 좌표 하나하나씩 순서대로 확인해서 변수에 +1, 혹은 -1을 하고 최댓값을 갱신하면 된다. 당연히 -1이 1보다 작으므로 먼저 계산되기 때문에 '선분의 끝 점에서..
[BOJ][Python] 백준 32454번 - Fibonacci Lucky Numbers 문제 링크: https://www.acmicpc.net/problem/32454 문제 풀이피사노 주기, 오일러 피 함수, 분할 정복을 이용한 거듭제곱 일단 $7^{7^{7^n}}$을 먼저 보면 벌써부터 답이 없어지는데, 이 수는 매우 크기 때문에 사실상 직접 구하는 것은 불가능하다. 그래서 접근하기가 힘든데, $7^{7^{7^n}}$번째 피보나치 수를 $10$번째 자리까지 출력하라고 적혀있다. 이 말은 피보나치 수를 구했을 때 $10^{10}$으로 나눈 값만 구하면 된다. 그렇다면 여기서 떠올리는 게 있다면 쭉쭉 풀려질 것이다. 피사노 주기를 이용하면 된다. 피보나치 수에서 나누는 값이 $10^{m} (m > 2)$라면 주기는 $15 \times 10^{m-1}$다. $m = 10$이므로 주기는 $15 ..
[BOJ][Python] 백준 32242번 - $Axy+Bx+Cy+D=0$ 문제 링크: https://www.acmicpc.net/problem/32242문제 풀이폴라드 로, 정수론 처음에는 서브테스크로 나눠서 생각을 해봤는데, $A$가 0이냐 0이 아니냐를 기준으로 나눠서 생각했다. 생각해야할 케이스가 매우 많으므로 천천히 생각해봐야 한다. 1. $A=0$인 경우1-1. $B \neq 0$, $C \neq 0$ 인 경우$Bx+Cy+D=0$의 형태가 되는데 베주 항등식이 떠오를 것이다. 정수 해가 무한히 존재하는 지 혹은 없는지에 대해 알 수 있다.$GCD(B, C) = X$라 하고, 베주 항등식에 따르면 $X$가 $D$의 배수이면 정수인 $x, y$가 무수히 많기 때문에, 이를 판별해서 구하면 된다. 1-2. $B = 0$, $C \neq 0$ 인 경우$Cy+D=0$이 되고,..
랜덤 마라톤 14주차 A. Card Game Contest (백준 14551)조합론 각각의 덱은 독립적이므로 총 방법의 수는 $A_1$부터 $A_N$까지 곱하면 된다. 단, 덱이 없을 수도 있는데, 이때는 스킵하거나 0을 1로 바꾸면 된다. $M$으로 나눈 나머지를 구해야 하므로 곱할 때마다 모듈러 연산을 취해주면 된다.  B. 행사장 대여 (Small) (백준 14732)구현 범위가 작으므로 좌표를 받을 때마다 그 부분의 영역들을 2차원 배열에 1로 채워주면 된다. 이후 넓이를 구할 때 1의 개수를 세어주면 된다. C. 체크포인트 달리기 (백준 29891)그리디, 정렬 일단 들어오는 모든 수가 양수 혹은 음수일 때를 생각해보면, $N$이 $K$의 배수라면 거리가 먼 순서부터 체크하던지, 가까운 순서부터  체크하던지 상관없지..
[BOJ][Python] 백준 3653번 - 영화 수집 문제 링크: https://www.acmicpc.net/problem/3653문제 풀이세그먼트 트리 N+M개의 배열을 생각해서 세그트리를 짜면 된다. 그리고 인덱스 배열을 하나 만들 건데 [0, n, n-1, n-2, ..., 1]로 만들어준다. 그 이유는 1이 가장 위에 있으므로 자신의 위쪽엔 아무것도 없다. 이를 배열로 생각하면 자신의 오른쪽에는 아무것도 없다라는 의미고 아래는 자신의 왼쪽이라고 생각하면 된다. 아무튼 인덱스가 지금 최대 n이니 책을 꺼냈다면 그 책의 인덱스는 이제 n+1이 되고 원래 있었던 인덱스의 세그 값은 0으로, 새롭게 만들어진 인덱스는 1로 업데이트 하면 문제에 대한 쿼리를 적절하게 수행할 수 있다.  코드
백준 문제 출제 후기 31472번 - 갈래의 색종이 자르기 31472번: 갈래의 색종이 자르기첫 번째 줄에 정수 $W$가 주어진다. ($2 \le W \le 20\,000$, $W$는 짝수) 항상 답이 존재하는 경우만 입력으로 주어진다.www.acmicpc.net 1회 양갈래 컵 A번 문제다. 가장 쉬운 문제인만큼 풀이도 쉽다. 원래 사각형의 절반 $W$가 주어지므로 2를 곱한 후 제곱근 해주면 한 변의 길이가 된다. 단, 출력할 때 정수로 출력하는 것을 잊지 말자. 이것 때문에 틀리신 분들이 조금 존재했고, 예제만 보시고 /3*4 하신 분들도 많았다. 여담으로 이 문제는 원래 점이 여러 개 주어지고 컨벡스 헐을 구한 후 반으로 나누고 컨벡스 헐 내부에 있는 점들이 반으로 나눈 선분의 왼쪽에 있는지 오른쪽에 있는지 판별하려는..
[BOJ] 2023 11월 3주차 정리 2023년 11월 13일 (월)  ~ 11월 19일 (일) - 푼 문제 (8 solved) 문제 링크: https://www.acmicpc.net/problem/13224 13224번: Chop CupOisín is amateur magician and is big fan of Chop Cup routine which involves three cups face down and one ball underneath one of the cups. He's only started to practice the trick and wants to test out if you can follow where the ball is without any trickswww.acmicpc.net 13324번 Chop Cup ..

티스토리툴바