주의사항
- JAVA를 사용하여 프로그램을 사용하였습니다.
- 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.
public class Main{
public static void main(String[] args){
}
}문제 설명
접근 방법
동적계획법이란 위 문제와 같이 동일한 연산을 계속 반복하여 비효율적으로 코드가 실행되어 그것을 향상시키기 위하여반복되는 연산의 결과를 따로 저장하여 적재적소에 코드가 더 효율적으로 만드는 방법입니다.
이 문제를 해결하는데 저는 냅색알고리즘을 사용하였습니다.
이전 단계 동적계획법 1에서 냅색알고리즘을 사용한 문제가 있었기 때문에 링크도 남겨드리겠습니다.
[백준] 단계별로 풀어보기(단계:15,동적계획법1,JAVA)12865번, 평범한 배낭
문제 링크 12865번: 평범한 배낭 www.acmicpc.net 주의사항 JAVA를 사용하여 프로그램을 사용하였습니다. 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다. public class M
tussle.tistory.com
저울에 구슬을 놓을 때에 최대의 가치를 넣을 때를 표로 만들었습니다.
표에서 열의 index값은 무게를 확인하는 구슬의 무게의 값이다.
예를 들어 index=4이면 최대무게가 4일 때 확인하는 구슬의 무게가 4인 값을 표현하는 것입니다.
표에서 행의 index값은 입력값에서 받은 무게 값에 대응하여 그 구술 이하의 무게들로 가치값을 구하는 것입니다.
예를 들어 구슬의 무게가 3, 4, 6일 때 index=2이면 2번째 입력되었던 무게 4가 대응되고 그 이하의 구슬로 무게가 3, 4인 구슬들로 확인하는 확인하는 구슬의 무게를 표현하는 것입니다.
예제입력2을 표로 살펴보면(찾는 값 1, 4, 10)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | |
| 2 | N | T | N | N | N | N | N | N | N | N | N | N | N | N | N | N |
| 3 | T | T | T | N | T | N | N | N | N | N | N | N | N | N | N | N |
| 3 | T | T | T | T | T | T | N | T | N | N | N | N | N | N | N | N |
| 3 | T | T | T | T | T | T | T | T | T | N | T | N | N | N | N | N |
※문제에서 추의 무게는 500g이하이며 개수가 30개이하여서 15000g까지 구슬의 무게를 측정할 수 있기 때문에 코드를 확인하시면 DP는 15501으로 초기화하였습니다.
※15001이 아닌 15501인 이유는 찾는 구슬의 무게 + 행의 대응하는 값의 최대가 15500이기 때문입니다.
문제를 해결한 알고리즘의 과정입니다.
1. DP[][]의 값을 -1로 초기화해줍니다.
2. DP[0][0]을 기준으로 재귀를 통해 팰린드롭이 맞는지 확인하였습니다.
3. DP가 -1이 아니면 해당 DP값을 반환하고 아니면 탐색을 진행합니다.
4. DP[S][E]을 결과로 출력합니다.
- BufferedReader를 사용하여 입력 값을 받았습니다.
- StringTokenizer을 이용하여 basicMarble, findMarble 배열을 초기화해주었습니다.
- 구슬 확인할 수 있는지 판단하는 Scale 함수를 만들었습니다.
- BufferedWriter에 findMarble 값의 따른 Y, N의 값을 저장하였습니다.
- BufferedWriter에 저장된 결과값을 출력하였습니다.
- palindrome은 반복을 통해 위 4가지 조건을 검사하여 구슬을 확인 가능한지 판단하였습니다.
결과 코드
import java.io.*;
import java.util.*;
public class Main{
public static int[] basicMarble; //추의 무게 저장하는 배열
public static int[] findMarble; //무게 찾는 구슬 값 저장하는 배열
public static boolean[][] DP; //무게 찾을 수 있는지 확인하는 배열
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//입력값 처리하는 BufferedReader
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
//결과값 출력하는 BufferedWriter
//----------입력값 저장 및 배열 초기화-------
int N = Integer.parseInt(br.readLine());
basicMarble = new int[N+1];
StringTokenizer st = new StringTokenizer(br.readLine()," ");
for(int i=1;i<=N;i++) {
basicMarble[i] = Integer.parseInt(st.nextToken());
}
int M = Integer.parseInt(br.readLine());
findMarble = new int[M];
st = new StringTokenizer(br.readLine()," ");
for(int i=0;i<M;i++) {
findMarble[i] = Integer.parseInt(st.nextToken());
if(findMarble[i]>15000) //최대값 15000벗어났을 때
findMarble[i] = -1;
}
DP = new boolean[N+1][15501];
Scale(N); //함수 실행
for(int i=0;i<M;i++) {
if(findMarble[i]==-1)
bw.write("N "); //15000이상은 무조건 N
else if(DP[N][findMarble[i]])
bw.write("Y "); //결과 Y 저장
else
bw.write("N "); //결과 N 저장
}
bw.flush(); //결과 출력
bw.close();
br.close();
}
//---------무게 확인할 수 있는지 판단하는 함수----------
public static void Scale(int N) {
for(int i=1;i<=N;i++) {
for(int j=1;j<=15000;j++) {
if(DP[i-1][j]) //조건 1.
DP[i][j] = true;
else {
int temp1 = Math.abs(j - basicMarble[i]); //조건 3의 관한 값
int temp2 = j + basicMarble[i]; //조건 4의 관한 값
if(temp1==0) //조건 2.
DP[i][j] = true;
else {
if(DP[i-1][temp1] || DP[i-1][temp2]) //조건 3과4
DP[i][j] = true;
}
}
}
}
}
}'정보처리기사' 카테고리의 다른 글
| 정보처리기사 실기(데이터 입·출력 구현) 이상/함수적 종속 (0) | 2022.03.16 |
|---|---|
| 정보처리기사 실기(데이터 입·출력 구현) 관계대수 및 관계해석 (0) | 2022.03.16 |
| 정보처리기사 실기(데이터 입·출력 구현) 관계형 데이터베이스의 제약 조건 - 무결성 (0) | 2022.03.15 |
| 정보처리기사 실기(데이터 입·출력 구현) 관계형 데이터 베이스의 제약 조건 - 키 (0) | 2022.03.15 |
| 정보처리기사 실기(데이터 입·출력 구현) 관계형 데이터베이스의 구조/ 관계형 데이터 모델 (0) | 2022.03.15 |
댓글