Gold(16)
-
BOJ 1153 - 네 개의 소수 (Python3)
그간 정말로 격조했다. 메이플스토리에 빠져서 며칠 간 헤어나오지를 못했다...! 이번 문제는 간단한 수학 문제다. 소수 판정과 관련된 약간 심화된 문제. 그러나 난이도는 그렇게 어렵지 않다. 비슷한 유형의 문제를 몇 풀어 봤다면 코드 복붙으로 일정 구간은 날로 먹을 수 있으니 말이다. 그럼 본격적으로 풀이에 돌입해 보자. 문제 임의의 자연수가 주어지면, 이를 네 개의 소수의 합으로 분해하는 프로그램을 작성하시오. 예를 들어 38 = 5 + 7 + 13 + 13이 된다. 입력 첫째 줄에 자연수 N(\(1 \le N \le 1\,000\,000\))이 주어진다. 예제 입력) 38 출력 첛째 줄에 네 개의 소수를 빈 칸을 사이에 두고 순서대로 출력한다. 불가능한 경우는 -1을 출력한다. 예제 출력) 5 7 1..
2023.01.17 -
BOJ 27087 - 직육면체 (Python3)
문제를 풀고 기여를 할 때마다 생각하는 것인데, 수학적으로 자명해 보이는 것이 실제로 그다지 자명하지 않은 경우 기여 편차는 하늘과 땅으로 갈린다. 내 눈에는 증명이 바로 보이지만 남의 눈에는 증명이 아예 안 보이는 경우가 많나 보다. 이 문제는 어제 개최된 SciOI 2022의 D번 문제이다. 개인적으로는 총 10개의 문제 중 가장 쉬웠다. 발상 난이도가 골드라는 건 절대 동의할 수 없다. 그럼 본격적으로 풀이에 돌입해 보자. 문제 A×B×C 모양의 직육면체를 1×p×p 모양의 직육면체로 채울 수 있는지 판별하시오. 단, p는 소수이다. 직육면체의 방향은 중요하지 않다. 즉, 직육면체를 돌려서 p×1×p, p×p×1로 채우는 것도 가능하다. 입력 첫 줄에 테스트 케이스의 수 T가 주어진다. 이후 한 줄..
2023.01.02 -
BOJ 2447 - 별 찍기 - 10 (Python3)
아직 시험이 절반밖에 지나지 않았다. 21일에 마지막 시험이 종료된다. 복수전공 예정인 과목인데다가 교수님에게 빌어넣어서 들어간 과목이다. 망칠 수는 없다. 빌어 넣은 사람에서 빌어먹은 사람이 되기 때문에... 그런고로 적당히 어려운 2447번 풀이를 올리고, 22일부터 왕성한 활동을 하도록 하겠다. 이번 문제는 별 찍기 문제. 무려 골드씩이나 되는 문제다! 그럼 본격적으로 풀이에 돌입해 보자. 문제 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다. *** * * *** N이 3보다 클 경우, 크기 N의 패턴은 공백으로..
2022.12.17 -
BOJ 15717 - 떡파이어 (Python3)
이 문제보다 더 어렵고 구현하기도 빡센 돌아온 떡파이어라는 문제가 있다. 접근법은 영 다르지만 문제의 백스토리라거나 하는 것은 거의 같으니... 이 문제의 경우 18291번 문제와 아주 유사한 풀이방법을 가지고 있다. 어떻게 답이 얻어지는지만 알면 말이다. 그럼 본격적으로 풀이에 돌입해 보자. 문제 떡파이어의 불로장생의 비밀은 바로 떡국이다. 떡파이어는 떡국을 먹은 그릇의 개수만큼 나이를 먹는다. 그들은 매일 떡국을 먹는데, 떡국을 먹는대로 바로 소화가 가능하기 때문에 하루에 얼마든지 원하는만큼 떡국을 먹을 수 있다. 그러나 전에 떡국을 얼마나 먹었든지, 그들은 기구하게도 떡국을 하루라도 먹지 않으면 생을 마감하게 된다. 어느 날, 디디는 어떤 떡파이어가 N세로 생을 마감하기까지 어떤 생을 살아왔는지 알..
2022.12.04 -
BOJ 7677 - Fibonacci (Python3)
분할 정복은 어떤 수의 거듭제곱만을 대상으로 하는 것이 아니다. 오히려 어떤 수의 거듭제곱보다는 행렬을 거듭제곱하는 것을 더욱 많이 볼 수 있다. 선형 점화식으로 주어진 수열일 경우 행렬을 거듭제곱함으로서 손 쉽게, 다이나믹 프로그래밍보다 훨씬 효율적으로, 매우 큰 n에 대하여 값을 구할 수 있다. 그럼 본격적으로 풀이에 돌입해 보자. 지문은 영어 한 줄, 해석 한 줄 번갈아서 표시된다. 문제 In the Fibonacci integer sequence, \(F_0 = 0, F_1 = 1\), and \(F_n = F_{n−1} + F_{n−2}\) for n ≥ 2. For example, the first ten terms of the Fibonacci sequence are: 0, 1, 1, 2, ..
2022.12.01 -
BOJ 16563 - 어려운 소인수분해 (Python3)
소인수분해는 프로그래머들과 뗄려야 뗄 수 없는 관계이다. RSA를 통한 암호와 복호화는 지금도 광범위하게 쓰이고 있고, 따라서 해커들에게는 더 빠른 소인수분해가, 보안 책임자들에게는 더 큰 소수가 필요하다. 범위가 정해진 많은 수의 소인수분해를 빠르게 할 수 있는 방법으로 N 이하의 수로 모두 나눠 보는 무식한 방법인 에라토스테네스의 체가 있다. 그리고 이 글에서 소개할 방법은 그 무식한 방법을 응용한 linear seive이다. 에라토스테네스의 체는 시간복잡도가 \(O(N\log\log N)\)이고 linear seive는 시간복잡도가 \(O(N)\)이라고 한다. 매우 큰 수에 대해서는 둘 다 시간을 많이 잡아먹기는 하겠지만, 5,000,000 정도의 매우 작은 수들에 대해서는 후자가 상당히 효율적이다..
2022.11.28