[Python] 백준 11051번 문제, 이항 계수 2
https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net N과 K를 입력 받아 nCk의 결과를 출력하는 문제이다. nCk는 n! / k!(n-k)!이다. (N과 K의 범위는 문제 참고) 그런데 N!, K!, (N-K)!를 구할 때 중복된 계산이 많기 때문에 비효율적이다. 그렇기 때문에 동적 프로그래밍을 이용한다면 효율적으로 계산할 수 있다. 나는 dp를 만들고 인덱스에 해당 팩토리얼 결과값을 넣었다. 예로 1번째 인덱스, 2번째 인덱스, 그리고 3번째 인덱스 값이 순서대로 1, 2, 6인데 3번째 인덱스 값을 구할 때, 1..
[Python] 백준 14651번 문제, 걷다보니 신척역 삼(Large)
https://www.acmicpc.net/problem/14651 14651번: 걷다보니 신천역 삼 (Large) 욱제는 ‘삼’이란 음절을 참 좋아한다. 인삼, 홍삼, 해삼, 삼성, 이춘삼(李春森), 삼식이, 삼시세끼, ㄴㄴ 그거 안 삼, 삼과 죽음, 알았삼, 걷다보니 신천역 삼, 그리고 특히 일이삼을 좋아한다. www.acmicpc.net 1부터 N자리까지의 1, 2, 0으로 구성된 3의 배수를 하나씩 구한다면, 실행 시간이 너무 길어 시간 초과가 뜰 것이다. 하나씩 다 구하면 시간 초과가 발생하기 때문에 뭔가 수학적 규칙을 찾아야한다. 수학적 규칙을 찾기 위해 조건에 맞는 낮은 자릿수를 직접 적어보자. N Result 1 0 2 2 3 6 4 18 5 54 이렇게 누적합이 생기는데 N자릿수의 값은 ..
