본문 바로가기

알고리즘/백준 문제 풀이

 (338)
[Text] 22311번 Maze 6 https://www.acmicpc.net/problem/22311 22311번: Maze 6 In southern Ontario, many corn farmers create cornstalk mazes like the one shown. The mazes are created in the fall, after the grain has been harvested. There is still time for you to help design the best maze ever for 2010. A field is covered with corn st www.acmicpc.net 22/09/27 코드를 짜지 않고도 충분히 손으로도 풀 수 있는 문제로, 같은 시리즈의 Maze 9문제와 함께 풀면 더욱 좋은 문..
[Python] 1437번 수 분해 https://www.acmicpc.net/problem/1437 1437번: 수 분해 첫째 줄에 음이 아닌 정수 N이 주어진다. N은 1,000,000보다 작거나 같다. www.acmicpc.net 22/09/27 증명하기에는 살짝 어려웠던 문제로, 기발한 아이디어가 돋보였던 문제이다. 문제 접근 방식: 이 문제를 처음 풀 때에 직관적으로 최대한 많은 수들로 나눠야 한다고 생각했다. 직관적으로 생각했을 때에도, 어떤 큰 숫자가 있으면 그 숫자를 작은 수 10개로 나눠서 곱하는 것과 큰 수 2개로 나누어서 곱하는 것을 비교했을 때, 당연히 전자가 더 크다고 생각했기 때문이다. 예를 들자면, 10을 2 + 2 + 2 + 2 + 2로 나누는 것과 5 + 5로 나누는 것을 비교했을 때, 2^5 > 5^2이다...
[Python] 2531번 회전 초밥 https://www.acmicpc.net/problem/2531 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net 22/09/26 숫자 제한이 작아서 투 포인터를 사용하지 않고도 그냥 브루트 포스로도 풀리는 문제이다. 단지 이 문제에서 난해한 점은 문제를 읽고 해석하는 점이다. 문제 접근 방식: 문제의 목적은 연속된 k개의 초밥을 먹을 때, 먹을 수 있는 초밥의 최대 종류가 몇 가지인지 구하는 것이다. 여기서 추가로 주어지는 정보는 초밥 쿠폰의 존재이다. 초밥 쿠폰은 내..
[Python] 21144번 Missing Number https://www.acmicpc.net/problem/21144 21144번: Missing Number You are teaching kindergarten! You wrote down the numbers from $1$ to $n$, in order, on a whiteboard. When you weren’t paying attention, one of your students erased one of the numbers. Can you tell which number your mischievous student erased? www.acmicpc.net 22/09/25 어렵게 생각하면 어려운 문제이고, 쉽게 생각하면 쉽게 풀 수 있는 좋은 문제인 것 같다. 문제 접근 방식: 나는 이 문제를..
[Python] 21919번 소수 최소 공배수 https://www.acmicpc.net/problem/21919 21919번: 소수 최소 공배수 수열 중에 소수는 2, 3, 5가 있다. www.acmicpc.net 22/09/25 간단한 에라토스테네스의 체 알고리즘을 적용하는 문제로, 그다지 어려운 문제는 아니다. 만약 에라토스테네스의 체 알고리즘을 잘 모르는 상태라면, 먼저 배우기를 권장한다. 문제 접근 방식: 수열들 중에서 소수들을 먼저 골라야 되고, 주어지는 숫자의 크기가 백만 이하이므로, 백만 개의 배열을 불러와 에라토스테네스의 체 알고리즘을 진행하여 소수들을 골라낸다. 이후 이 소수들의 최소공배수를 구하는 것이 우리의 목적이다. 근데 우리는 소수들끼리는 모두 최대공약수가 1이라는 사실을 알고 있다. 때문에 최소 공배수를 구하려면 그냥 그 ..
[Python] 9918번 Cube / 2642번 전개도 https://www.acmicpc.net/problem/9918 9918번: Cube Folding six squares connected in some special ways can form a cube. For example, in the diagram below, the six squares on the left can be folded into a cube (with face 1 opposite face 4, face 2 opposite face 6, and face 3 opposite face 5) but the six squ www.acmicpc.net https://www.acmicpc.net/problem/2642 2642번: 전개도 입력은 여섯 줄로 되어 있으며 각 줄에는 0에서 6까지..
[Python] 14382번 숫자세는 양 (Large) https://www.acmicpc.net/problem/14382 14382번: 숫자세는 양 (Large) 예제 입출력 1번에 대해서, 2 × 0 = 0, 3 × 0 = 0 등등으로 이어지므로, 블리트릭스는 0외에는 다른 숫자를 기록할 수 없을 것이며, 따라서 영원히 잠에 들 수 없다. 예제 입출력 2번의 경우, 1, 2, 3, 4, www.acmicpc.net 22/09/25 단순한 시뮬레이션 문제로, 엄밀한 증명은 하지 않았으나 누구나 쉽게 떠올릴 법한 풀이로 해결한 문제이다. 문제 접근 방식: 먼저 문제에서 주어진 것처럼 계속 숫자를 키워나가며 수를 기록해갔다. 근데, INSOMNIA를 어떻게 판단하느냐가 관건이였다. 영원히 잠에 들지 못하면 INSOMNIA를 출력한다고 했는데, 반복문으로는 영원..
[Python] 23629번 이 얼마나 끔찍하고 무시무시한 수식이니 https://www.acmicpc.net/problem/23629

티스토리툴바