728x90
https://www.acmicpc.net/problem/5557
5557번: 1학년
상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀
www.acmicpc.net
728x90
메모리: 14,300 KB , 시간: 128 ms
사용 알고리즘: 다이나믹 프로그래밍
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.HashMap; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); int[] arr = new int[N]; StringTokenizer st = new StringTokenizer(br.readLine()); for (int i = 0; i < N; i++) { arr[i] = Integer.parseInt(st.nextToken()); } HashMap<Integer, Long> map = new HashMap<>(); map.put(arr[0], 1L); HashMap<Integer, Long> tmp; int sum, sub; for (int i = 1; i < N - 1; i++) { tmp = new HashMap<>(); for(int key : map.keySet()) { sum = key + arr[i]; sub = key - arr[i]; if(sum <= 20) { tmp.put(sum, tmp.getOrDefault(sum, 0L) + map.get(key)); } if(sub >= 0) { tmp.put(sub, tmp.getOrDefault(sub, 0L) + map.get(key)); } } map = tmp; } long result = map.get(arr[N - 1]); System.out.println(result); } }
728x90
'Problem Solving > BOJ' 카테고리의 다른 글
[백준, BOJ 2624] 동전 바꿔주기 (java) (0) | 2024.04.30 |
---|---|
[백준, BOJ 2613] 숫자구슬 (java) (0) | 2024.04.30 |
[백준, BOJ 1414] 불우이웃돕기 (java) (0) | 2024.04.19 |
[백준, BOJ 16434] 드래곤 앤 던전 (java) (1) | 2024.04.19 |
백준, BOJ 14657] 준오는 최종인재야!! (java) (0) | 2024.04.19 |