5557번: 1학년
상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀
www.acmicpc.net
- 생각
다시 풀어보려했는데 실패했다.. 다른 사람이 정리해 놓은 걸로 이해하였다.
상근이는 덧셈, 뺄셈을 통해 줄 지어진 숫자를 연산하여 가장 마지막 숫자가 나오도록 하고자 한다.
그러나, 연산 도중에 나올 수 있는 숫자는 0이상 20이하라고 한다.
여기서 크기가 21인 배열을 생각할 수 있다.
예시인 "8 3 2 4 8 7 2 4 0 8 8" 을 생각해보자.
처음 8이 올 때, 8이 될 수 있는 경우의 수는 1이다.
8 다음 3이 올 때, 3에서 할 수 있는 연산은 +3, -3 이다.
그 다음 2가 올 때 할 수 있는 연산은 +2, -2 이다.
4가 올 때 할 수 있는 연산은 +4, -4 로 범위를 넘어가면 빼주면 된다.
[BOJ] 백준 5557 - 1학년
백준 5557 - 1학년 상근이는 덧셈, 뺄셈을 통해 줄 지어진 숫자를 연산하여 가장 마지막 숫자가 나오도록 하고자 한다. 그러나, 연산 도중에 나올 수 있는 숫자는 0이상 20이하라고 한다. 여기서
hyunah030.tistory.com
- 코드
정답 코드 : dp[i][j] = j번 계산했을때 숫자 i값이 나올 수 있는 경우의 수로 N-1번 돌렸을 때 dp[array[N - 1]][N - 2]의 값을 얻어온다.
import java.io.IOException;
import java.io.InputStream;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static int N;
static long[][] dp;
static int[] array;
public static void main(String[] args) throws Exception {
SetData();
System.out.println(dp[N-2][array[N-1]]);
}
private static void SetData() throws Exception {
InputReader in = new InputReader(System.in);
N = in.nextInt();
dp = new long[N][21];
array = new int[N];
for(int i = 0; i < N; i++) {
array[i]= in.nextInt();
}
dp[0][array[0]]=1;
for(int i = 1; i < N; i++) {
for(int j = 0; j <= 20; j++) {
if(dp[i-1][j] != 0) {
if(j+array[i] <= 20) {
dp[i][j+array[i]] += dp[i-1][j];
}
if(j-array[i] >= 0) {
dp[i][j-array[i]] += dp[i-1][j];
}
}
}
}
}
}
class InputReader {
private final InputStream stream;
private final byte[] buf = new byte[8192];
private int curChar, snumChars;
public InputReader(InputStream st) {
this.stream = st;
}
public int read() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
snumChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (snumChars <= 0)
return -1;
}
return buf[curChar++];
}
public int nextInt() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public long nextLong() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public int[] nextIntArray(int n) {
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = nextInt();
}
return a;
}
public String nextLine() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isEndOfLine(c));
return res.toString();
}
public boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
private boolean isEndOfLine(int c) {
return c == '\n' || c == '\r' || c == -1;
}
}'algorithm' 카테고리의 다른 글
| [BOJ/JAVA] 백준 13977번 : 이항 계수와 쿼리 (0) | 2021.02.25 |
|---|---|
| [BOJ/JAVA] 백준 4963번 : 섬의 개수 (0) | 2021.02.24 |
| [BOJ/JAVA] 백준 1027번 : 고층 건물 (0) | 2021.02.22 |
| [BOJ/JAVA] 백준 1012번 : 유기농 배추 (0) | 2021.02.19 |
| [BOJ/JAVA] 백준 2579번 : 계단 오르기 (0) | 2021.02.18 |
