반응형 동적 프로그래밍3 #1354 무한 수열 2(Dynamic Programming) 이번 문제는 #1351과 같은 문제이지만, 숫자 범위가 좀 더 커지고, 두개의 숫자 인덱스를 계산하는 것이 좀 다릅니다. 그러다 보니 제한시간이 2초에서 10초로 대폭 늘었습니다. 난이도도 Gold IV에서 Gold III로 조금 높게 평가되었습니다. 그렇지만 똑같이 동적 프로그래밍을 이용하고 있고, 동적 프로그래밍상 히트율이 많이 낮아져서 시간이 많이 걸립니다. 제가 작성한 소스입니다. 소스는 참고용으로 봐주세요. //---------------------------------------------------------- // baekjoon #1354 - Infinity Series 2 // - by Aubrey Choi // - created at 2020-02-02 //---------------.. 2020. 2. 2. #1309 동물원(Dynamic Programming) 이번 문제는 Silver I 문제입니다. 이 문제를 풀기 위해서는 적절한 식을 세워야 하는데, 이것이 어느정도 훈련이 되지 않으면, 어렵습니다. 동적 프로그래밍은 점화식이 주어지지 않는 경우가 많습니다. 사실 동적 프로그래밍 뿐만 아니라 분할정복 관련된 문제들이 대부분 그렇습니다. 문제에서 식을 유도하고, 그 식을 수학적으로 정리하는 것이 필요합니다. 문제 난이도는 높지 않지만, 수학적으로 식을 유도하고, 정리하는 것이 필요해서 그 과정을 설명하고자 합니다. 2xN 동물원에 사자를 배치하는데, 가로와 세로로 연달아 배치 못하게 하는 경우의 수는 얼마인가가 문제입니다. 2칸씩 N개가 세로로 배치되는 것이니까, 2칸에 대해서 나올 수 있는 상태는 사자가 하나도 없는 경우, 사자가 왼쪽에 있는 경우, 사자가 .. 2020. 1. 19. #76 합의 경우의 수(Dynamic Programming) 이번 문제는 경우의 수를 계산하는 것입니다. 보통 분할(partition) 문제는 중복조합, 조합, 순열 등의 기법이 사용될 수 있지만, 이 문제와 같은 경우에는 분할이 쉽지 않습니다. 문제는 짧은 편입니다. N이란 숫자가 주어지면, 1부터 N-1 까지의 숫자중 2개 이상을 선택해서 그 합이 N이 되도록 하는 경우의 수를 찾는 것입니다. 예를 들어서 N=5라고 한다면, \( 5 = 1 + 1 + 1 + 1 + 1 \) \( 5 = 1 + 1 + 1 + 2 \) \( 5 = 1 + 1 + 3 \) \( 5 = 1 + 4 \) \( 5 = 1 + 2 +2 \) \( 5 = 2+ 3 \) 위와 같이 총 6가지가 나옵니다. 이 문제에서는 N=100일 때의 경우의 수가 얼마인지 계산하라는 문제입니다. 문제의 원본.. 2020. 1. 15. 이전 1 다음 728x90
