전체 글

[Python] 1629 - 곱셈 (실버1)

1. 문제 설명 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 2. 아이디어 반복문으로 풀면 무조건 타임에러가 난다. A = 2,147,483,647 / B = 2,147,483,647 / C = 1 인 테스트 케이스가 들어오면 약 21억번의 연산이 들어가기 때문에 O(n)으로는 풀 수 없다. 그래서 분할 정복(O(logn))으로 풀어야 타임 에러에서 벗어날 수 있다. 예를 들어, \(2^{10}\)은 \(2^{5}\) x \(2^{5}\)로 나눌 수 있다. 홀수인 경우에는 \(2^{11} = 2^{5}\)..

[Python] 1022 - 소용돌이 예쁘게 출력하기 (골드4)

1. 문제 설명 https://www.acmicpc.net/problem/1022 1022번: 소용돌이 예쁘게 출력하기 첫째 줄에 네 정수 r1, c1, r2, c2가 주어진다. www.acmicpc.net 정말 기억에 오래 남는 문제다. 이 문제를 풀기 위해서 12시간을 스카에 박혀있다가 결국 해결 못 하고 다음날 12시간을 더 할애했던 문제였었다. 순전히 PyPy로 시간 초과를 극복하는 것은 자존심이 허락하지 않는다는 얼토당토 않는 이유에서였다.. 2. 아이디어 이 문제는 풀이 방법이 2가지가 있다. (물론 더 있을 수 있지만, 난 모르겠다.) 하나는 무식하게 진짜 소용돌이를 다 '그려보는 것'이고, 다른 하나는 수학적으로 접근하여 위치를 추적하여 값을 출력하는 것이다. 전자는 당연히 시간초과가 나서..

[Python] 2133 - 타일 채우기 (골드4)

1. 문제 설명 https://www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 실버의 타일링(BOJ - 1793) 문제를 풀어봤다면 쉽게 해결할 수 있는 문제 2. 아이디어 어느정도 패턴 분석이 될 때까지는 노가다를 해봐야 하는 문제다. N이 홀수인 경우에는 절대 타일을 모두 채울 수 없으므로 0을 출력 후 프로그램을 종료하면 된다. 그럼 결국 남는 경우의 수는 N이 짝수인 경우일 뿐인데 N이 2, 4 정도는 직접 세볼 수 있지만 6만 넘어가도 41가지 경우가 나온다. 처음에 규칙성을 찾기가 굉장히 힘들지만 표를 그려서 색칠해보면 이해하기 쉽다. 2x3 블럭이 만나면 ..

[Python] 1788 - 피보나치 수의 확장 (실버3)

1. 문제 설명 https://www.acmicpc.net/problem/1788 1788번: 피보나치 수의 확장 첫째 줄에 F(n)이 양수이면 1, 0이면 0, 음수이면 -1을 출력한다. 둘째 줄에는 F(n)의 절댓값을 출력한다. 이 수가 충분히 커질 수 있으므로, 절댓값을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 2. 아이디어 헷갈린다면 직접 피보나치 수의 음수부를 써보면 이해가 갈 것이다. 패턴은 같은데 번갈아가며 음수값이 나옴을 확인할 수 있다. n이 0보다 작으면서 짝수번째에는 무조건 -1을 출력하고 시작하면 나머지는 그냥 피보나치 수열 문제와 다를 것이 없다. 그리고 나는 아마 이때쯤에 모듈러 연산이라는 개념을 알게되었던 것 같다. 쉽지만 굉장히 중요한..