글 읽기 - 5557번1학년 문제도와주세용

fdjk2000 2년 전 0

if(j+arr[i]<=20) dp[i][j+arr[i]]+=1;
if(j-arr[i]>=0) dp[i][j-arr[i]]+=1;

이게아니고왜

if(j+arr[i]<=20) dp[i][j+arr[i]]+=dp[i-1][j];
if(j-arr[i]>=0) dp[i][j-arr[i]]+= dp[i-1][j];

이거인거죠??

i번째에서 4가되는 숫자 횟수를 늘리는거아닌가요??

package back;

import java.util.Scanner;

public class DP_first {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int num = sc.nextInt();
		int[] arr = new int[num];
		for (int i = 0; i < num; i++) {
			arr[i] = sc.nextInt();
		}
		int[][] dp = new int[num][21];
		dp[0][8]=1;
		for (int i = 1; i < num; i++) {
			for (int j = 0; j < 21; j++) {
					if(dp[i-1][j]>= 1) {
						if(j+arr[i]<=20)  dp[i][j+arr[i]]+=1;
						if(j-arr[i]>=0) dp[i][j-arr[i]]+=1;
						
						
					}
			}
		}
		System.out.println(dp[num-1][arr[num-1]]);

	}

}

djm03178 2년 전 0

dp[i-1][j]는 i-1번째 수까지 계산했을 때 값이 j가 되는 경우의 수를 담고 있습니다.

i-1번째 수까지 계산해서 j가 되었을 때 여기에 arr[i]를 더하면 i번째 수까지 계산했을 때 j+arr[i]가 되고, 이렇게 되는 경우의 수는 dp[i-1][j]와 같습니다. 그래서 이 수를 더해줘야 합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

5557번1학년 문제도와주세용

fdjk2000 2년 전 0

djm03178 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말