알고리즘
백준 #9095: 1,2,3 더하기
난이도 : 실버3소요시간 : 23m사용한 풀이법 : DP풀이 과정dp[1] = 1 => 1 dp[2] = 1+1, 2 => 2 dp[3] = 1+1+1, 1+2, 2+1, 3 => 4 dp[4] = 1+1+1+1, 1+1+2, 1+2+1, 1+3, 2+1+1, 2+2, 3+1 => 7위의 식을 잘 보면 1로 시작하는 건 곧 1+3 인거라서 3을 이루는 덧셈의 경우의 수, 즉 dp[3]만 알면 됨 2로 시작하는건 2+2라서 dp[2]만 알면되고 3으로 시작하는건 dp[1]만 알면 됨.dp[5]를 예시로 들어보자1+…. 일때는 4를 이루는 경우들만 알면 됨 ⇒ dp[4] == dp[5-1]2+…. 일때는 3을 이루는 경우들만 알면 됨 ⇒ dp[3] == dp[5-2]3+…. 일때는 2를 이루는 경우들만 알..
2024. 3. 6. 23:14