DP3 [Python] 백준 9465번 (스티커) 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다. 모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다. 먼저, 그림 (b)와 같이 각 스티커에 점수를 매겼다. 상냥이가 뗄 수 있는 스티커의 점수의 최댓값을 구하는 프로그램을 작성하시오. 즉, 2n개의 스티커 중에서 점수의 합이 최대가 되면서 서로 .. 2021. 11. 21. [Python] 백준 (1, 2, 3 더하기) 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. 예제 입력 1 3 4 7 10 예제 출력 1 7 44 274 풀이방법 점화식을 추론하자 A1 A2 A3 A4 1 1+ A(1) -> (A1) = 1가지 1+(A2) -> (A.. 2021. 10. 25. [Python] 백준 (다리놓기) DP, 조합 문제풀이 조금 생각하다 보니 조합 문제임을 알 수 있었다. n < m 이기 때문에 최대 연결할 수 있는 다리는 n개 이다. m개 지역에 n개의 다리를 연결하는 경우의 수 조합: 집합에서 서로 다른 n개의 원소 중에서 순서에 상관없이 r개를 선택하는 것이다. mCn이 만들어짐 itertools의 combinations를 쓰면 제한시간(0.5초)에 걸려 해결 할 수 없음 직접 만들어쓰자..! 분자 denominator은 m*(m-1)*(m-2)*...*(m-n) 까지의 값 분모 numerator은 n! import sys T = int(sys.stdin.readline().rstrip()) answer = [] for i in range(T): denominator = 1 numerator = 1 N, M .. 2021. 10. 25. 이전 1 다음
