[Java] 백준 5557 1학년

Lee GaEun·2024년 10월 24일

JAVA 알고리즘 백준

[Java] 알고리즘

목록 보기

5/93

5557 1학년 문제 링크

문제분석

숫자 N개가 주어짐
숫자(1~(N-1)) 모두를 덧셈 혹은 뺄셈 연산하여 그 결과가 마지막 숫자여야 함
계산 중에 나오는 수는 0~20 범위 안이여야 함

입력 조건

첫째 줄 : 숫자의 개수
둘째 줄~ : 숫자 (공백으로 구분)

출력 조건

개수를 출력

#1

Main

i=1;
wht = calculate(리스트 첫숫자a, 리스트, i)

calculate

result1 = a+리스트[i]
result1이 0~20 사이의 수이면
- i++;
- if(i==(N-2))
  - if(result1==리스트[N-1]) return 1;
    - else return 0;
- answer(전역변수) += calculate(result1, 리스트, i)
result2 = a-리스트[i]
result2이 0~20 사이의 수이면
- i++;
- if(i==(N-2))
  - if(result==리스트[N-1]) return 1;
    - else return 0;
- answer(전역변수) += calculate(result1, 리스트, i)
아니면 return 0

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static Scanner num = new Scanner(System.in);

    static int N = num.nextInt();
    static int answer = 0;

    public static void main(String[] args) {

        int[] nList = new int[N];

        for(int i=0; i<N; i++) {
            nList[i] = num.nextInt();
        }

        int c = 1;
        calculate(nList[0], nList, c);

        System.out.println(answer);
    }

    public static void calculate(int result, int[] nList, int i) {
        int result1 = result+nList[i];
        int result2 = result-nList[i];
        i++;

        if(0 <= result1 && result1 <= 20) {
            if(i==(N-1)) {
                if(result1==nList[N-1]) answer+= 1;
            }
            else calculate(result1, nList, i);
        }

        if(0 <= result2 && result2 <= 20) {
            if(i==(N-1)) {
                if(result2==nList[N-1]) answer += 1;
            }
            else calculate(result2, nList, i);
        }
    }
}

길이가 짧은 예제1은 성공인데 길이기 긴 예제2는 너무 오래 걸림

#2

DP(Dynamic Programming)

: 큰 문제를 작은 단위로 쪼개 그 결과를 저장 후 재활용하여 답을 도출

DP의 사용 조건
1) Overlapping Subproblems : 같은 계산이 중복됨
2) Optimal Substructure : 부분 문제의 결과가 전체 문제의 최적 답임

Main

int[] nList = new int[N]; // 수가 담겨있는 리스트
int[][] result = new int[N][21]; // 결과 리스트 생성
result[0]nList[0]] += 1;
calculate(result);
result[N-2]nList[N-1]] 출력

calculate

for(c<N-2)
for(i<21), if(result[c][i] > 0)
- if ( nList[c-1]+nList[c]<=20 )
  - result[c]nList[c-1]+nList[c]] += 1;
- if ( 0<=nList[c-1]-nList[c] )
  - result[c]nList[c-1]-nList[c]] += 1;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static Scanner num = new Scanner(System.in);
    static int N = num.nextInt();

    public static void main(String[] args) {

        int[] nList = new int[N];
        int[][] result = new int[N][21];

        for(int i=0; i<N; i++) {
            nList[i] = num.nextInt();
        }

        result[0][nList[0]] = 1;
        calculate(result, nList);

        System.out.println(result[N-2][nList[N-1]]);
    }

    public static void calculate(int[][] result, int[] nList) {
        for(int c=1; c<N-1; c++) {
            for(int i=0; i<21; i++) {
                if(result[c-1][i] > 0) {
                    if((i+nList[c])<=20) {
                        result[c][i+nList[c]] += result[c-1][i];
                    }
                    if(0<=(i-nList[c])) {
                        result[c][i-nList[c]] += result[c-1][i];
                    }

                }
            }
        }
    }
}

코드는 제대로 완성된 것 같은데
예제2번의 답이 제대로 출력되지 않았다
그래서 코드를 한줄씩 디버깅함
숫자가 너무 커서 int가 제대로 받아주지 못함을 확인

#3

Long vs long

Long

참조 타입 : 메모리 주소 값을 통해 객체를 참조

null 값을 가질 수 있음 (기본 값 = null)

id 값으로 자주 쓰임

long

원시 타입 : 실제 메모리에 데이터를 직접 저장

null 값을 가질 수 없음 (기본 값 = 0)

int vs long

int

정수 (32bit)

-2147483648 ~ 2147483647

long

정수 (64bit)

-9223372036854775808 ~ 9223372036854775807

int에 비해 메모리 많이 차지함 , 느림

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static Scanner num = new Scanner(System.in);
    static int N = num.nextInt();

    public static void main(String[] args) {

        int[] nList = new int[N];
        long[][] result = new long[N][21];

        for(int i=0; i<N; i++) {
            nList[i] = num.nextInt();
        }

        result[0][nList[0]] = 1;
        calculate(result, nList);

        System.out.println(result[N-2][nList[N-1]]);
    }

    public static void calculate(long[][] result, int[] nList) {
        for(int c=1; c<N-1; c++) {
            for(int i=0; i<21; i++) {
                if(result[c-1][i] > 0) {
                    if((i+nList[c])<=20) {
                        result[c][i+nList[c]] += result[c-1][i];
                    }
                    if(0<=(i-nList[c])) {
                        result[c][i-nList[c]] += result[c-1][i];
                    }

                }
            }
        }
    }
}