[JAVA]백준 5557번: 1학년

www.acmicpc.net/problem/5557

5557번: 1학년

 

1. 문제 설명

 

숫자가 주어질 때 +,-만 사용하여 만들 수 있는 올바른 등식의 수를 구하는 문제이다.

 

재귀함수와 for문을 이용하여 풀었다.

 

1) 재귀 함수 점화식

 

x가 인덱스 번호, y가 현재까지 합이라고 한다면

cache[x][y]=cache[x+1][y+list[x+1]]+cache[x+1][y-list[x+1]] 이다.

 

 

 

2) for문 점화식

 

x가 현재 인덱스 번호, y가 인덱스 x-1까지의 합이라고 한다면

 

cache[x][y+list[x]]+=cache[x-1][y]

cache[x][y-list[x]]+=cache[x-1][y]이다.

 

두 방식 모두 시간 복잡도는 O(N)이다.

 

2. 코드

 

1) 재귀 함수

import java.awt.image.BufferedImageFilter;
import java.io.*;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static int N;
    public static int target;

    public static int[] list=new int[101];

    public static Long[][] cache=new Long[101][21];


    public static void main(String[] args) throws IOException {
        Scanner scan = new Scanner(System.in);

        N=scan.nextInt();

        for(int index=0;index<N-1;index++)
            list[index]=scan.nextInt();

        target=scan.nextInt();

        for(int x=0;x<=100;x++){
            for(int y=0;y<=20;y++)
                cache[x][y]=0L;
        }

        System.out.print(make_bag(0,list[0]));

        scan.close();


    }

    public static long make_bag(int index,int sum){

        if(index==N-2){
            if(sum==target)
                return 1L;
            else
                return 0L;
        }

        if(sum>20L)
            return 0L;

        if(cache[index][sum]!=0L)
            return cache[index][sum];

        long ret=0L;

        if(sum+list[index+1]<=20L)
            ret+=make_bag(index+1,sum+list[index+1]);

        if(sum-list[index+1]>=0L)
            ret+=make_bag(index+1,sum-list[index+1]);

        cache[index][sum]=ret;

        return ret;

    }

}

2) for문

import java.awt.image.BufferedImageFilter;
import java.io.*;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static int N;
    public static int target;

    public static int[] list=new int[101];

    public static Long[][] cache=new Long[101][21];


    public static void main(String[] args) throws IOException {
        Scanner scan = new Scanner(System.in);

        N=scan.nextInt();

        for(int index=0;index<N-1;index++)
            list[index]=scan.nextInt();

        target=scan.nextInt();

        for(int x=0;x<=100;x++){
            for(int y=0;y<=20;y++)
                cache[x][y]=0L;
        }

        cache[0][list[0]]=1L;

        for(int x=1;x<N-1;x++){

            int plus=list[x];

            for(int y=0;y<=20;y++){

                long temp=cache[x-1][y];

                if(temp!=0L){
                    if(y+plus<=20)
                        cache[x][plus+y]+=temp;
                    if(y-plus>=0)
                        cache[x][y-plus]+=temp;

                }
            }
        }

        System.out.println(cache[N-2][target]);

        scan.close();


    }


}