![](https://blog.kakaocdn.net/dn/bzKxP2/btslK7DpXlJ/LVe7tkBCaexBS9wM2xEQWK/img.jpg)
1. 문제
5557번: 1학년
상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀
www.acmicpc.net
상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀고 있다. 예를 들어, "8 3 2 4 8 7 2 4 0 8 8"에서 등식 "8+3-2-4+8-7-2-4-0+8=8"을 만들 수 있다.
상근이는 올바른 등식을 만들려고 한다. 상근이는 아직 학교에서 음수를 배우지 않았고, 20을 넘는 수는 모른다. 따라서, 왼쪽부터 계산할 때, 중간에 나오는 수가 모두 0 이상 20 이하이어야 한다. 예를 들어, "8+3+2-4-8-7+2+4+0+8=8"은 올바른 등식이지만, 8+3+2-4-8-7이 음수이기 때문에, 상근이가 만들 수 없는 등식이다.
숫자가 주어졌을 때, 상근이가 만들 수 있는 올바른 등식의 수를 구하는 프로그램을 작성하시오.
2. 풀이
long타입 2차원배열 dp를 만든다. dp[i][j]는 i번째 숫자를 가지고 결과 j(0<=j<=20)를 만든 경우의 수다.
첫 번째 숫자는 연산 없이 고정이라 dp[0][첫번째숫자]에 1을 저장하고 시작한다.
dp를 채울 때 순서대로 연산해야하기 때문에 가장 바깥 반복문은 숫자의 인덱스만큼 탐색한다. 단, 가장 마지막 숫자는 탐색할 필요 없다.(등호사용하기 때문)
idx마다 0부터 20까지 탐색하는데, 이 수는 이전idx에서 나온 결과들이라고 보면 된다.
만약 dp[idx-1][num]==0이라면 이전 idx에서 만들어지지 않았다는 의미이므로 다음 수로 넘어간다.
num+현재숫자가 0이상 20이하일때 dp[idx][새 숫자]에 이전idx결과 경우의 수를 더한다.
dp를 다 채웠다면 답을 출력해야한다.
dp[마지막에서 두번째 숫자idx][가장 마지막 숫자]는 마지막에서 두번째 숫자에서 가장 마지막 숫자로 연산되는 경우의 수가 담겨있다.
dp[N-2][number[N-1]]을 출력한다.
import java.io.*;
import java.util.*;
public class BOJ_5557_1학년 {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(in.readLine());
int[] number = new int[N];
StringTokenizer st = new StringTokenizer(in.readLine());
for(int i=0;i<N;i++) number[i] = Integer.parseInt(st.nextToken());
long[][] dp = new long[N][21];
dp[0][number[0]] = 1;
for(int idx=1;idx<N-1;idx++){
for(int num=0;num<21;num++){//이전값
if(dp[idx-1][num]==0) continue;
if(num+number[idx] < 21) dp[idx][num+number[idx]] += dp[idx-1][num];
if(num-number[idx] > -1) dp[idx][num-number[idx]] += dp[idx-1][num];
}
}
System.out.println(dp[N-2][number[N-1]]);
}
}
3. 결과
![](https://blog.kakaocdn.net/dn/9CQsv/btslFkK4qYS/kdVietSv9uQKMTtKnMwvsK/img.png)
재귀로 푸려다가 너무 오래 시간이 걸리는 걸 보고 빠르게 접었다.
역시 이렇게 숫자가 큰 건 의심하고 봐야한다.
'코딩테스트 > BOJ' 카테고리의 다른 글
[BOJ] 1516 게임 개발 - JAVA (0) | 2023.07.02 |
---|---|
[BOJ] 13301 타일 장식물 - JAVA (0) | 2023.07.01 |
[BOJ] 9625 BABBA - JAVA (0) | 2023.06.29 |
[BOJ] 1202 보석 도둑 - JAVA (0) | 2023.06.28 |
[BOJ] 1937 욕심쟁이 판다 - JAVA (0) | 2023.06.27 |
댓글