문제 링크
16457번: 단풍잎 이야기
첫째 줄에 키의 개수 n, 퀘스트의 개수 m, 퀘스트 당 사용해야 하는 스킬의 수 k가 주어진다. n은 10 이하, k는 n 이하의 양의 정수이며, m은 100 이하의 양의 정수이다. 둘째 줄부터 m개의 줄에는 각각
www.acmicpc.net
주의사항
- JAVA를 사용하여 프로그램을 사용하였습니다.
- 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.
public class Main{
public static void main(String[] args){
}
}문제 설명
접근 방법
이 문제에 핵심
1. 2n개의 스킬이 존재하지만, 키보드에는 n개의 스킬만 키세팅을 할 수 있습니다.
2. m개의 퀘스트는 완료하기 위해서는 k개의 스킬의 수가 필요합니다.
3. 최적의 키배치를 했을 때 깰 수 있는 퀘스트의 최대 개수를 결과로 출력합니다.
알고리즘 진행 순서.
1. 입력된 정보를 저장합니다.
2. 스킬 키배치의 조합을 만들어서, 퀘스트 클리어에 대한 최대 개수를 탐색합니다.
3. 탐색을 통해 얻은 퀘스트 완료 최대 개수를 결과로 출력합니다.
스킬 키배치 조합
n이 2일 때 스킬은 4개이며, 배치할 수 있는 스킬은 아래와 같다.
(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)
즉, 각 스킬의 조합을 만들수 있으며, 이는 재귀 탐색을 통해서 구할 수 있습니다.
또한, 저는 각 스킬이 채택되었는지에 대해서 비트마스킹으로 진행하였습니다.
만약, 2번째 스킬이 채택되었을 때에는
100이 됩니다.
2, 4번째 스킬이 채택된다면
10100이 됩니다.
이렇게 비트 마스킹으로 각 스킬이 배치되었는지 표현하였습니다.
완료할 수 있는 퀘스트 구하기
완료할 수 있는 퀘스트 개수를 구하는 과정은, 각 비트에 맞는 값이 존재하는지 확인합니다.
예제입력 1.
1. 입력된 정보를 저장합니다.
n : 3
m : 4
k : 2
퀘스트
| 요구 스킬 | |
| 퀘스트 1 | 1, 3 |
| 퀘스트 2 | 1, 2 |
| 퀘스트 3 | 2, 3 |
| 퀘스트 4 | 3, 6 |
2. 스킬 키배치의 조합을 만들어서, 퀘스트 클리어에 대한 최대 개수를 탐색합니다.
n이 3이므로 존재하는 스킬은 6개(2n)입니다.
(1, 2, 3)일 때
▶ 정답이 될 때에만 진행되는 과정을 보여드리겠습니다.
| 요구 스킬 | |
| 퀘스트 1 | 1, 3 |
| 퀘스트 2 | 1, 2 |
| 퀘스트 3 | 2, 3 |
| 퀘스트 4 | 3, 6 |
퀘스트 1 : (1, 3) : O
1110 & 10 = 2
▶ 1번 스킬은 채택되었습니다.
1110 & 1000 = 8
▶ 3번 스킬은 채택되었습니다.
퀘스트 2 : (1, 2) : O
1110 & 10 = 2
▶ 1번 스킬은 채택되었습니다.
1110 & 100 = 4
▶ 2번 스킬은 채택되었습니다.
퀘스트 3 : (2, 3) : O
1110 & 100 = 4
▶ 2번 스킬은 채택되었습니다.
1110 & 1000 = 8
▶ 3번 스킬은 채택되었습니다.
퀘스트 4 : (3, 6) : X
1110 & 1000 = 8
▶ 3번 스킬은 채택되었습니다.
1110 & 1000000 = 0
▶ 6번 스킬은 채택되지 않았습니다.
총 3개의 퀘스트 완료!
3. 탐색을 통해 얻은 퀘스트 완료 최대 개수를 결과로 출력합니다.
탐색을 통해 얻은 최대 퀘스트 완료 개수 : 3개
- BufferedReader를 사용하여 입력되는 정보를 저장합니다.
- StringTokenizer를 이용하여 스킬 및 퀘스트 정보를 띄어쓰기 기준 나누었습니다.
- search를 이용하여 키세팅 조합에 따른 최대 퀘스트 클리어 개수를 탐색합니다.
- 탐색한 최대 퀘스트 클리어 개수를 Bufferedwriter 저장합니다.
- BufferedWriter에 저장된 결과를 출력합니다.
- search함수는 재귀를 통해 키세팅의 조합을 진행합니다.
- check함수는 키셋팅에 따른 퀘스트 완료 개수를 구한 뒤 최대와 비교합니다.
결과코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class Main {
static int result = Integer.MIN_VALUE;
static int[][] quest;
static int n,m,k;
public static void main(String[] args) throws IOException {
//입력값 처리하는 BufferedReader
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//결과값 출력하는 BufferedWriter
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine()," ");
//입력값 저장
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
quest = new int[m][k];
//퀘스트 저장
for(int i=0;i<m;i++){
st = new StringTokenizer(br.readLine()," ");
for(int j=0;j<k;j++){
quest[i][j] = Integer.parseInt(st.nextToken());
}
}
//키셋팅 조합으로 퀘스트 최대 완료 개수 탐색 진행
search(0,1, 0);
bw.write(String.valueOf(result)); //최대 퀘스트 완료 개수 BufferedWriter 저장
bw.flush(); //결과 출력
bw.close();
br.close();
}
//키셋팅 조합 진행하는 재귀 함수
static void search(int idx, int cur, int bit){
//키셋팅 완료시
if(idx == n){
check(bit);
return;
}
//더 이상 만들 수 없는 경우
if(cur > 2 * n){
return;
}
//키 조합하기
search(idx+1, cur+1, bit | (1<<cur));
search(idx, cur+1, bit);
}
//현재 키세팅으로 퀘스트 완료 개수 구하는 함수
static void check(int bit){
int cnt = 0;
for(int i=0;i<m;i++){
boolean flag = false;
for(int j=0;j<k;j++){
//해당 스킬 채택되었는지 AND 연산으로 확인
if(((1<<quest[i][j]) & bit) == 0){
flag = true;
break;
}
}
//해당 퀘스트 완료 가능시
if(!flag){
cnt++;
}
}
//최대 퀘스트 개수 비교
result = Math.max(result, cnt);
}
}'백준' 카테고리의 다른 글
| [백준, Java] 24551번, 일이 너무 많아..., (정수론) (2) | 2024.04.25 |
|---|---|
| [백준, Java] 25330번, SHOW ME THE DUNGEON, (백트래킹) (0) | 2024.04.17 |
| [백준, Java] 1527번, 금민수의 개수, (백트래킹) (0) | 2024.04.08 |
| [백준, Java] 24954번, 물약 구매, (백트래킹) (0) | 2024.04.02 |
| [백준, Java] 28437번, 막대 만들기, (DP) (0) | 2024.03.25 |
댓글