각 재료의 맛 점수 합을 더해가면서 제한 칼로리를 넘지않는 최대 합을 구한다. dfs를 사용하여, 순서대로 맛 점수를 더해 최대 칼로리보다 작으면서 가장 큰 값이 나오는 경우를 계산한다. 해당 재료를 넣었을 때와 넣지 않은 경우의 수를 각각 계산하여 maxScore를 리턴하면 끝!
import java.util.*;
import java.io.*;
public class Main{
static int[][] food;
static int maxScore;
static int maxCal;
public static void main(String[]args) throws NumberFormatException, IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int tc = Integer.parseInt(br.readLine());
for(int k=1;k<=tc;k++){
String[] NL = br.readLine().split(" ");
maxCal = Integer.parseInt(NL[1]);
//맛 점수와 칼로리를 넣을 배열 생성
food = new int[Integer.parseInt(NL[0])][2];
for(int i=0;i<Integer.parseInt(NL[0]);i++){
String[]str = br.readLine().split(" ");
food[i][0] = Integer.parseInt(str[0]);
food[i][1] = Integer.parseInt(str[1]);
}
calculate(0,0,0);
System.out.println("#"+k+" "+maxScore);
}//tc
}//main
static void calculate(int idx, int score, int cal){
if(cal>maxcal){
return
}else if(score>maxScore){
maxScore = score;
}
if(idx==food.length)return;
calculate(idx+1,score+food[idx][0],cal+food[idx][1]);
calculate(idx+1,score,cal);
}
}//class
인접리스트를 활용한 BFS방법으로 풀었다. 큐에는 단순 숫자를 넣어 해당 숫자에 대한 접근 여부를 확인하여, 접근하지 않았을 경우 큐에 넣고 넘어간다. 큐가 비어있지 않을 경우, 사이즈를 확인하여, 해당 노드들이 각각 손을 뻗치는 순간을 한 턴으로 생각하였다. 매 턴마다 ANSWER변수를 0으로 초기화해주고, 그 턴에서 가장 큰 값을 저장한다. 마지막 턴에서 가장 큰 값을 출력하였다.
단순하게 큐대신 PQ에 넣어서 마지막에 나오는 값을 출력하면 어떨까 생각해보았는데, 이러면 무조건 나올수 있는 가장 큰 값이 마지막에 출력되게 되어 자꾸 100을 답으로 내뱉었다... 일반적인 큐로 하니 잘 돌아갔당
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
public classSWEA1238_Contact {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuffer sb = new StringBuffer();
for (int tc = 1; tc < 11; tc++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int S = Integer.parseInt(st.nextToken());
ArrayList<Integer>[] list = new ArrayList[101];
boolean[] visited = new boolean[101];
//I에서 갈수 있는 노드를 모두 LIST[I]에 넣는다.
st = new StringTokenizer(br.readLine());
for (int i = 0; i < 101; i++) {
list[i] = new ArrayList<>();
}
//FROM,TO를 합쳐서 N개이기 때문에 N/2만큼의 크기만 있으면 된다.
for (int i = 0; i < N / 2; i++) {
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
if (!list[from].contains(to)) {
list[from].add(to);
}
}
Queue<Integer> q = new ArrayDeque<>();
q.add(S);
visited[S] = true;
int max = Integer.MIN_VALUE;
while (!q.isEmpty()) {
int answer = 0;
int size = q.size();
//이번 턴에서 가장 큰 값을 ANSWER에 저장. 저장된 ANSWER를 MAX로 보낸다.
//MAX는 매턴마다 덮어쓰여진다.
for (int j = 0; j < size; j++) {
int tmp = q.poll();
answer = Math.max(tmp, answer);
max = answer;
//이번 큐에서 갈 수 있는 노드중 방문하지 않았던 노드를 큐에 저장
for (int i : list[tmp]) {
if (!visited[i]) {
q.add(i);
visited[i] = true;
}
}
}
}
sb.append("#").append(tc).append(" ").append(max).append("\n");
}
System.out.println(sb);
}// main
}// class
수연이가 악마의 손아귀를 피해 여신님이 계신 곳으로 이동해야하는 문제이다. 악마의 손아귀는 사방으로 이동하기 때문에 이를 표현해주기 위해 BFS를 이용하여 풀었다. 수연이가 여신님께 도달할 수 있는 최소 시간을 구해야하기 때문에 POINT안에 TIME변수를 설정해주고 한 턴이 끝날 때마다 1씩 증가해서 큐에 넣어준다.
악마의 큐와 수연이의 큐를 따로 설정한 후, 해당 TIME에서 각각 큐에 들어있는 값들이 돌맹이가 있는 지점('.')으로만 이동할 수 있게 했다. 악마를 먼저 이동시키고, 악마가 가지 않은 곳에 수연이가 이동할 수 있도록 하였다. 만약 수연이가 여신님을 만나게 되면 해당 time을 answer에 저장해주고 return한다. 반면, 수연이가 이동할 수 있는 곳이 없게 되면 수연이의 queue가 비게 되고, solve안에 있는 while문이 끝나게 된다. 이 경우 answer에 값이 담기지 않아 GAMEOVER를 출력하게 된다.
package 김영서;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;
public class Solution {
static int N, M, answer, move[][];
static char map[][];
static Queue<Point> sq, dq;
static void solve() {
while (!sq.isEmpty()) {
int d = dq.size();
for (int j = 0; j < d; j++) {// 악마 사방탐색 -> 현재 악마가 움직일 수 있는만큼만 가기
Point tmp = dq.poll();
for (int i = 0; i < 4; i++) {
int nr = tmp.r + move[i][0];
int nc = tmp.c + move[i][1];
if (nc >= 0 && nr < N && nr >= 0 && nc < M &&(map[nr][nc] == '.' || map[nr][nc] == 'S')) {
//System.out.println("D"+tmp.r + " " + tmp.c);
Point newP = new Point(nr, nc);
map[nr][nc] = '*';
dq.add(newP);
}
}
} // 악마 for
// 수연이가 이동할 수 있는 경로로 움직이기...!
d = sq.size();
for (int j = 0; j < d; j++) {
Point tmp = sq.poll();
for (int i = 0; i < 4; i++) {
int nr = tmp.r + move[i][0];
int nc = tmp.c + move[i][1];
if (nc >= 0 && nr < N && nr >= 0 && nc < M && (map[nr][nc] == '.' || map[nr][nc] == 'D')) {
// System.out.println("S"+nr+" "+nc+" "+tmp.time);
Point newP = new Point(nr, nc, tmp.time+1);
if (map[newP.r][newP.c] == 'D') {// 여신님과 만났으면 빠져나가기?
answer = tmp.time;
return;
}
map[nr][nc]='S';
sq.add(newP);
}
}
}
}
}
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
int T = Integer.parseInt(br.readLine());
for (int tc = 1; tc <= T; tc++) {
answer=0;
int[] NM = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
N = NM[0];
M = NM[1];
map = new char[N][M];
move = new int[][] { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
sq = new ArrayDeque<Point>();
dq = new ArrayDeque<Point>();
for (int i = 0; i < N; i++) {
String str = br.readLine();
for (int j = 0; j < M; j++) {
map[i] = str.toCharArray();
if (map[i][j] == 'S') {
sq.add(new Point(i, j, 1));
} else if (map[i][j] == '*') {
dq.add(new Point(i, j));
}
}
}
// System.out.println(Arrays.deepToString(map));
solve();
if(answer==0) {
System.out.println("#" + tc + " GAME OVER");
}else {
System.out.println("#" + tc + " " + answer);
}
}
}
static class Point {
int r, c, time;
public Point(int r, int c, int time) {
super();
this.r = r;
this.c = c;
this.time = time;
}
public Point(int r, int c) {
super();
this.r = r;
this.c = c;
}
}
}
처음에 문제 내용이 잘 이해가 안되어서 반복해서 읽어따.. 문제의 핵심은 선택한 위치부터 그 뒤로 다 같은 값을 넣는다는 것이다. 문제에 나와있는 예시처럼 0100의 경우 3번째 bit를 골라 1로 설정하게 되면 0111이 된다. 모든 bit이 0으로 초기화 된 상태에서 원래 상태로 되돌리면 된다!
처음엔 Int로 값을 받았는데, 그렇게 하니 0110같은 경우를 110으로 처리해버려서 char로 배열을 설정해주었다. 앞에서 부터 값을 비교해가면서 원래 값과 다를 경우 리스트를 계속 갱신해 가는 식으로 문제를 풀었다.
import java.util.Arrays;
import java.util.Scanner;
public class P001_SWEA1289_원재의메모리복구하기 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
for (int i = 0; i < num; i++) {
String memory = sc.next();
int answer = 0;
char[] tmp = new char[memory.length()];
Arrays.fill(tmp, '0');
for (int j = 0; j < memory.length(); j++) {
if (memory.charAt(j) == '1' && tmp[j] == '0') {
answer += 1;
Arrays.fill(tmp, j, tmp.length, '1');
} else if (memory.charAt(j) == '0' && tmp[j] == '1') {
answer += 1;
Arrays.fill(tmp, j, tmp.length, '0');
}
}
System.out.println("#num" + (i + 1) + " " + answer);
}
}
}
처음에는 단순하게 일차원 배열을 생성해서 1일권과 1달권을 비교해서 작은 값을 넣은 후, 3달권과 3달의 값의 합을 비교하는 형태로 풀었다. 이렇게 풀면 3달권을 계산할 때 제대로 값을 계산하지 못한다.ㅠ
1
2
3
4
10
20
20
30
예를 들어 위의 경우 아래층에 적힌 숫자가 한달권의 가격이라고 했을 때, 1,2,3월을 3달권으로 끊고, 4월을 1달권으로 끊는 것 보다 1월을 1달권으로 끊고 2,3,4월을 3달권으로 끊는 것이 더 유리하다. DFS나 BFS로 풀어서 최소값을 구하는 것도 가능할 것 같은데, 여기서는 Dynamic Programing 기법을 사용해보았다.
새로운 배열 monthAns를 생성하여, 해당 월까지의 최소 비용을 저장한다. 1월, 2월은 1일권*수영한 날 vs 1달권을 비교해서 넣고, 3월은 (1) 1일권*수영한 날 vs 1달권 비교 (2) vs 3달권 비교로 계산해주었다. 4월부터 12월까지는 (1) 1일권과 1달권 비교하여 해당 달의 최소 비용 + 전달까지의 최소값 (2)vs 해당 달을 포함하여 3달권 사용 + n-3월까지의 최소값으로 계산하였다. 그리고 monthAns의 11번째 값과 1년권을 비교하여 출력하였다. 1일권과 1달권의 값 비교는 계속 진행하여서 3월달까지는 쉽게 이해될 것 같으니 넘어가고, 4월달부터 12월을 그림으로 설명해보겠다.
위에서 설명한 것 처럼 4월달의 최소 비용은 3월까지의 최소비용+4월의 최소비용 vs 1월까지의 최소비용+ (2,3,4의 값 vs 3개월 권) 으로 계산된다. 이어 5월의 최소비용은 4월까지의 최소값 5월의 최소비용 vs (5월을 포함한 3달의 값 vs3개월권) 으로 계산하여 더 작은 값을 monthAns배열에 넣어준다. 같은 동작을 12월까지 수행하고, 그 값을 1년권과 비교하여 출력하면 끝이다!
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class SWEA1952_수영장 {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int t = Integer.parseInt(br.readLine());
for (int tc = 1; tc <= t; tc++) {
int answer = Integer.MAX_VALUE;
int[] price = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
int[] swim = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
int[] monthAns = new int[14];
//1일권, 1달권, 3달권
monthAns[0]=Math.min(price[0]*swim[0],price[1]);
monthAns[1]=monthAns[0]+Math.min(price[0]*swim[1],price[1]);
monthAns[2]=+Math.min(monthAns[1]+Math.min(price[0]*swim[2],price[1]), price[2]);
//4월 가능한 경우: 1월까지의 최소값+3개월권. 3월까지의 최소값+4월의 계산 값
// monthAns[3]=Math.max(monthAns[3-3]+price[2],monthAns[3-1]+Math.max(price[1]*swim[3],price[1]));
//5월 가능한 경우: 2월까지의 최소값+3개월권. 4월까지의 최소값+5월의 계산값
// monthAns[4]=Math.max(monthAns[1]+price[2],monthAns[3]+Math.max(price[0]*swim[4],price[1]));
for(int i=3;i<12;i++) {
monthAns[i]=Math.min(monthAns[i-3]+price[2],monthAns[i-1]+Math.min(price[0]*swim[i],price[1]));
}
answer = Math.min(monthAns[11], price[3]);
sb.append("#").append(tc).append(" ").append(answer).append("\n");
}
System.out.println(sb);
}// main
}// class
