코딩 상자

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWT-lPB6dHUDFAVT 

평소 햄버거를 좋아하던 민기는 최근 부쩍 늘어난 살 때문에 걱정이 많다.

그렇다고 햄버거를 포기할 수 없었던 민기는 햄버거의 맛은 최대한 유지하면서 정해진 칼로리를 넘지 않는 햄버거를 주문하여 먹으려고 한다.

민기가 주로 이용하는 햄버거 가게에서는 고객이 원하는 조합으로 햄버거를 만들어서 준다.

하지만 재료는 미리 만들어서 준비해놓기 때문에 조합에 들어가는 재료를 잘라서 조합해주지는 않고, 재료를 선택하면 준비해놓은 재료를 그대로 사용하여 조합해준다. 

민기는 이 가게에서 자신이 먹었던 햄버거의 재료에 대한 맛을 자신의 오랜 경험을 통해 점수를 매겨놓았다.

민기의 햄버거 재료에 대한 점수와 가게에서 제공하는 재료에 대한 칼로리가 주어졌을 때,

민기가 좋아하는 햄버거를 먹으면서도 다이어트에 성공할 수 있도록 정해진 칼로리 이하의 조합 중에서 민기가 가장 선호하는 햄버거를 조합해주는 프로그램을 만들어보자.

(단 여러 재료를 조합하였을 햄버거의 선호도는 조합된 재료들의 맛에 대한 점수의 합으로 결정되고, 같은 재료를 여러 번 사용할 수 없으며, 햄버거의 조합의 제한은 칼로리를 제외하고는 없다.)

 

[입력]
 

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
 

각 테스트 케이스의 첫 번째 줄에는 재료의 수, 제한 칼로리를 나타내는 N, L(1 ≤ N ≤ 20, 1 ≤ L ≤ 104)가 공백으로 구분되어 주어진다.
 

다음 N개의 줄에는 재료에 대한 민기의 맛에 대한 점수와 칼로리를 나타내는 Ti, Ki(1 ≤ Ti ≤ 103, 1 ≤ Ki ≤ 103)가 공백으로 구분되어 주어진다.
 

[출력]

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 주어진 제한 칼로리 이하의 조합중에서 가장 맛에 대한 점수가 높은 햄버거의 점수를 출력한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Burger {
	static int N;	// 재료의 수
	static int T;	// 제한 칼로리
	static int Max; // 제한 칼로리 이하의 조합중 최대 맛 총점

	// 매개변수
	// int sum_k = 선택한 원소들의 칼로리 합계
	// int[][] num = 선택 대상 배열
	// int cnt = 선택 수행 횟수
	// boolean[] isSelected = 선택 True&False 저장 배열
	public static void powerSet(int sum_k, int[][] num, int cnt, boolean[] isSelected) {
		if (cnt == N) {		// 재료의 수만큼 선택하는 행위를 완료
			if (sum_k > T)	// 제한 칼로리 이상->중지
				return;		// 맛 총점 계산과 Max 갱신 코드를 수행하지 않도록 return
			// 맛총점 계산, Max 갱신
			int sum_t = 0; // 맛 총점
			for (int i = 0; i < N; i++) { 	// isSelected를 탐색해서
				if (isSelected[i]) { 		// 선택된 원소일 경우
					sum_t += num[i][0]; 	// 맛총점에 점수 add
				}
			}
			if (Max <= sum_t)	// 맛 총점이 max 이상일 경우
				Max = sum_t;	// max를 맛 총점으로 갱신
			return;				// cnt가 N이므로 더이상 powerset을 호출하지 않도록 return
		}
		// cnt가 N이 아니면 선택, 비선택 powerset 호출
		isSelected[cnt] = true;
		powerSet(sum_k + num[cnt][1], num, cnt + 1, isSelected);	// 선택한 경우이므로 칼로리 합계에 선택된 원소의 칼로리 add
		isSelected[cnt] = false;
		powerSet(sum_k, num, cnt + 1, isSelected);					// 비선택한 경우이므로 칼로리 합계는 그대로
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		int TC = Integer.parseInt(br.readLine());	// Testcase 수 입력

		for (int t = 1; t <= TC; t++) {
			Max = Integer.MIN_VALUE;				// Testcase 마다 Max를 Integer의 최솟값으로 갱신
			sb.append("#" + t + " ");
			String str = br.readLine();
			st = new StringTokenizer(str, " ");
			N = Integer.parseInt(st.nextToken());	// 재료의 수 입력
			T = Integer.parseInt(st.nextToken());	// 제한 칼로리 수 입력
			
			// tk 배열에 재료의 수만큼 맛 점수와 칼로리를 입력받음
			int[][] tk = new int[N][2];
			for (int n = 0; n < N; n++) {
				str = br.readLine();
				st = new StringTokenizer(str, " ");
				tk[n][0] = Integer.parseInt(st.nextToken());
				tk[n][1] = Integer.parseInt(st.nextToken());
			}
			
			powerSet(0, tk, 0, new boolean[N]);		//칼로리 합계 0, cnt 0으로 powerset 호출
			sb.append(Max + "\n");					//sb에 갱신된 Max값과 개행문자 삽입
		}
		System.out.println(sb);
	}
}

https://www.acmicpc.net/problem/2605

문제

점심시간이 되면 반 학생 모두가 한 줄로 줄을 서서 급식을 탄다. 그런데 매일 같이 앞자리에 앉은 학생들이 앞에 줄을 서 먼저 점심을 먹고, 뒷자리에 앉은 학생들은 뒤에 줄을 서 늦게 점심을 먹게 된다. 어떻게 하면 이러한 상황을 바꾸어 볼 수 있을까 고민하던 중 선생님이 한 가지 방법을 내 놓았다. 그 방법은 다음과 같다.

학생들이 한 줄로 줄을 선 후, 첫 번째 학생부터 차례로 번호를 뽑는다. 첫 번째로 줄을 선 학생은 무조건 0번 번호를 받아 제일 앞에 줄을 선다. 두 번째로 줄을 선 학생은 0번 또는 1번 둘 중 하나의 번호를 뽑는다. 0번을 뽑으면 그 자리에 그대로 있고, 1번을 뽑으면 바로 앞의 학생 앞으로 가서 줄을 선다. 세 번째로 줄을 선 학생은 0, 1 또는 2 중 하나의 번호를 뽑는다. 그리고 뽑은 번호만큼 앞자리로 가서 줄을 선다. 마지막에 줄을 선 학생까지 이와 같은 방식으로 뽑은 번호만큼 앞으로 가서 줄을 서게 된다. 각자 뽑은 번호는 자신이 처음에 선 순서보다는 작은 수이다.

예를 들어 5명의 학생이 줄을 서고, 첫 번째로 줄을 선 학생부터 다섯 번째로 줄을 선 학생까지 차례로 0, 1, 1, 3, 2번의 번호를 뽑았다고 하자, 첫 번째 학생부터 다섯 번째 학생까지 1부터 5로 표시하면 학생들이 줄을 선 순서는 다음과 같이 된다.

• 첫 번째 학생이 번호를 뽑은 후 : 1
• 두 번째 학생이 번호를 뽑은 후 : 2 1
• 세 번째 학생이 번호를 뽑은 후 : 2 3 1
• 네 번째 학생이 번호를 뽑은 후 : 4 2 3 1
• 다섯 번째 학생이 번호를 뽑은 후 : 4 2 5 3 1

따라서 최종적으로 학생들이 줄을 선 순서는 4, 2, 5, 3, 1이 된다.

줄을 선 학생들이 차례로 뽑은 번호가 주어질 때 학생들이 최종적으로 줄을 선 순서를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 학생의 수가 주어지고 둘째 줄에는 줄을 선 차례대로 학생들이 뽑은 번호가 주어진다. 학생의 수가 100 이하이고, 학생들이 뽑는 번호는 0 또는 자연수이며 학생들이 뽑은 번호 사이에는 빈 칸이 하나씩 있다.

출력

학생들이 처음에 줄을 선 순서대로 1번부터 번호를 매길 때, 첫째 줄에 학생들이 최종적으로 줄을 선 순서를 그 번호로 출력한다. 학생 번호 사이에는 한 칸의 공백을 출력한다.

import java.util.Scanner;

public class Line {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		int N = sc.nextInt();
		int[] arr = new int[N];
		int[] result = new int[N];
		for (int n = 0; n < N; n++) {
			arr[n] = sc.nextInt();
		}
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < arr[i]; j++) {
				result[i-j] = result[i-j-1];
			}
			result[i-arr[i]] = i+1;
		}
		for(int i = 0; i < N; i++) {
			if(i == N-1) sb.append(result[i]);
			else sb.append(result[i]+" ");		
		}
		System.out.println(sb);
	}
}

본인보다 앞에 있는 원소들 중, 맨 뒤 원소부터 뽑은 수만큼 한개씩 뒤로 밀어주고 자신은 뽑은 수 만큼 앞으로 값을 대입해 주었습니다.

for (int i = 0; i < N; i++) {
for (int j = 0; j < arr[i]; j++) {
result[i-j] = result[i-j-1];
}
result[i-arr[i]] = i+1;
}

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LtJYKDzsDFAXc 

N2개의 방이 N×N형태로 늘어서 있다.

위에서 i번째 줄의 왼쪽에서 j번째 방에는 1이상 N2 이하의 수 Ai,j가 적혀 있으며, 이 숫자는 모든 방에 대해 서로 다르다.

당신이 어떤 방에 있다면, 상하좌우에 있는 다른 방으로 이동할 수 있다.

물론 이동하려는 방이 존재해야 하고, 이동하려는 방에 적힌 숫자가 현재 방에 적힌 숫자보다 정확히 1 더 커야 한다.

처음 어떤 수가 적힌 방에서 있어야 가장 많은 개수의 방을 이동할 수 있는지 구하는 프로그램을 작성하라.


[입력]

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 하나의 정수 N (1 ≤ N ≤ 103)이 주어진다.

다음 N개의 줄에는 i번째 줄에는 N개의 정수 Ai, 1, … , Ai, N (1 ≤ Ai, j ≤ N2) 이 공백 하나로 구분되어 주어진다.

Ai, j는 모두 서로 다른 수이다.


[출력]

각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고,

한 칸을 띄운 후, 처음에 출발해야 하는 방 번호와 최대 몇 개의 방을 이동할 수 있는지를 공백으로 구분하여 출력한다.

이동할 수 있는 방의 개수가 최대인 방이 여럿이라면 그 중에서 적힌 수가 가장 작은 것을 출력한다.

import java.util.Scanner;

public class Solution {
	static int R[] = { -1, 1, 0, 0 };
	static int C[] = { 0, 0, -1, 1 };
	static int max;

	private static void dfs(int[][] arr, int r, int c, int N) {

		for (int i = 0; i < 4; i++) {
			int nr = R[i] + r;
			int nc = C[i] + c;
			if (nr < 0 || nc < 0 || nr >= N || nc >= N)
				continue;
			if (arr[nr][nc] != arr[r][c] + 1)
				continue;
			dfs(arr, nr, nc, N);
			max++;
			break;
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		int T = sc.nextInt();
		int N;
		int[][] arr;
		for (int t = 0; t < T; t++) {
			N = sc.nextInt();
			arr = new int[N][N];
			sb.append("#" + (t + 1) + " ");

			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					arr[i][j] = sc.nextInt();
				}
			}
			int answerMax = 0;
			int a = Integer.MAX_VALUE;

			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					max = 1;
					dfs(arr, i, j, N);
					if (answerMax < max) {
						answerMax = max;
						a = arr[i][j];
					} else if (answerMax == max) {
						if (a >= arr[i][j])
							a = arr[i][j];
					}
				}
			}
			sb.append(a + " ");
			sb.append(answerMax + "\n");
		}
		System.out.println(sb);
	}
}

경계를 벗어나지 않는 사방탐색 결과 현재 원소보다 1큰 값이 있으면 해당방향으로 이동한 뒤 재귀함수를 호출해주었습니다.

max++을 통해 이동가능한 최대 블럭 수를 세어주었습니다.

이동할 수 있는 방의 개수가 최대인 방이 여럿이라면 그 중에서 적힌 수가 가장 작은 것을 출력해야하므로 

//이 조건문에서 최대값을 갱신해주고

if (answerMax < max) {
answerMax = max;
a = arr[i][j];
} 

//이 조건문에서 a를 max가 같은 것들 중, 적힌 수가 가장 작은 것으로 갱신해 주었습니다.

else if (answerMax == max) {
if (a >= arr[i][j])
a = arr[i][j];
}

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWGsRbk6AQIDFAVW 

카드를 퍼펙트 셔플 한다는 것은, 카드 덱을 정확히 절반으로 나누고 나눈 것들에서 교대로 카드를 뽑아 새로운 덱을 만드는 것을 의미한다. 

정확한 방식은 다음 그림과 같다.

N개의 카드가 있는 덱이 주어질 때 이를 퍼펙트 셔플하면 어떤 순서가 되는지 출력하는 프로그램을 작성하라.

만약 N이 홀수이면, 교대로 놓을 때 먼저 놓는 쪽에 한 장이 더 들어가게 하면 된다.


[입력]

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 자연수 N(1 ≤ N ≤ 1,000)이 주어진다.

두 번째 줄에는 덱에 카드가 놓인 순서대로 N개의 카드 이름이 공백으로 구분되어 주어진다.

카드의 이름은 알파벳 대문자와 ‘-’만으로 이루어져 있으며, 길이는 80이하이다.

[출력]

각 테스트 케이스마다 주어진 덱을 퍼펙트 셔플한 결과를 한 줄에 카드 이름을 공백으로 구분하여 출력한다.

import java.util.Scanner;

public class suffle {
	public static void main(String[] args) {
	      Scanner sc = new Scanner(System.in);
	      StringBuilder sb = new StringBuilder();
	      int T = sc.nextInt();
	      int N;
	      String[] arr;
	      String[] front;
	      String[] behind;
	      for (int t = 0; t < T; t++) {
	         N = sc.nextInt();
	         sc.nextLine();
	         arr = new String[N];
	         for (int n = 0; n < N; n++) {
	            arr[n] = sc.next();
	         }
	         front = new String[arr.length / 2 + arr.length % 2];
	         behind = new String[arr.length / 2];
	         for (int i = 0; i < front.length; i++) {
	            front[i] = arr[i];
	         }
	         for (int i = 0; i < behind.length; i++) {
	            behind[i] = arr[front.length + i];
	         }
	         for (int i = 1, j = 0; i <= arr.length; i++) {
	            if (i % 2 == 1)
	               arr[i - 1] = front[j];
	            else {
	               arr[i - 1] = behind[j];
	               j++;
	            }
	         }
	         sb.append("#" + (t + 1) + " ");
	         for (int i = 0; i < arr.length; i++) {
	            sb.append(arr[i] + " ");
	         }
	         sb.append("\n");
	      }
	      System.out.println(sb);
	   }
}

입력받은 배열을 front 배열과 behind 배열로 나누어 저장해주었습니다.

//arr의 원소 갯수가 홀수이면 front가 원소를 하나 더 가져야 하므로 new String[arr.length / 2 + arr.length % 2]로 생성해 주었습니다.

front = new String[arr.length / 2 + arr.length % 2];

behind = new String[arr.length / 2];

//arr[0]~arr[front.length-1]까지 front에 저장
for (int i = 0; i < front.length; i++) {
     front[i] = arr[i];
}

//arr[front.length + 0]~arr[front.length+behind.length-1]까지 behind에 저장
for (int i = 0; i < behind.length; i++) {
     behind[i] = arr[front.length + i];
}

//i는 1부터 arr.length 이하. 홀수 번째에는 arr[i-1]에 front를 저장하고, 짝수번째에는 behind를 저장
for (int i = 1, j = 0; i <= arr.length; i++) {
     if (i % 2 == 1)
     arr[i - 1] = front[j];
     else {
           arr[i - 1] = behind[j];
           j++;
     }
}