분할정복(2)
-
백준 2201번, 이친수 찾기 풀이
문제 백준 2201번 풀이 길이가 $ 1, 2, 3, 4, 5 $인 이친수들을 모두 적어보겠습니다. $ 1 $ $ 10 $ $ 100, 101 $ $ 1000, 1001, 1010 $ $ 10000, 10001, 10010, 10100, 10101 $ 이며 각각의 개수는 $ 1, 1, 2, 3, 5 $와 같습니다. 대충 규칙이 피보나치 수열과 같다는 것을 볼 수 있습니다. 길이가 $K$인 이친수의 개수가 피보나치 수열의 원소와 같다는 믿음을 가지면 아래 문제를 푸는 것으로 바꿀 수 있습니다. $N$번째 이친수의 길이는 몇인가? 이는 피보나치 수열을 한번 돌리면 길이를 구할 수 있습니다. 다음은, 길이가 $ K ( K \geq 2) $인 경우 이친수는 "항상" 앞이 10으로 시작합니다. (이친수의 시작은 ..
2021.02.05 -
2020 부산코딩경진대회 후기 / 풀이
문제 난이도는 솔브드 기준으로 1,2,3,4번 순서대로 브론즈 / 실버 / 골드 / 플레로 잘 배분된 것 같았습니다. 1번은 정사각형의 변 길이를 2 ~ $ min(N, M) $ 잡고 삼중 for 돌리면 됩니다. 시간 복잡도는 $ O(N^3) $ 가 됩니다. 2번은 투포인터 또는 분할 정복을 사용하면 됩니다. 비슷한 문제: https://www.acmicpc.net/problem/2003 3번은 $ M $번째 쓰레기가 어디서 태워지는지 알아야하는데, 대부분 최소 공배수로 접근한 것 같습나다. 그리고 대부분이 못 푼 것 같습니다. TMI로 최소공배수를 사용한 접근 방법은 잘 모르겠으나 최소 공배수로 하면 소수(prime number)로 구성된 저격 테케를 만들면, 최소 공배수의 범위가 $ unsig..
2020.09.27