코딩 상자

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

문제

크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다.

이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.

임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다.

예를 들어, 아래와 같은 지도를 갖는 도시를 살펴보자.

0 2 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 2

0은 빈 칸, 1은 집, 2는 치킨집이다.

(2, 1)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |2-1| + |1-2| = 2, (5, 5)에 있는 치킨집과의 거리는 |2-5| + |1-5| = 7이다. 따라서, (2, 1)에 있는 집의 치킨 거리는 2이다.

(5, 4)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |5-1| + |4-2| = 6, (5, 5)에 있는 치킨집과의 거리는 |5-5| + |4-5| = 1이다. 따라서, (5, 4)에 있는 집의 치킨 거리는 1이다.

이 도시에 있는 치킨집은 모두 같은 프랜차이즈이다. 프렌차이즈 본사에서는 수익을 증가시키기 위해 일부 치킨집을 폐업시키려고 한다. 오랜 연구 끝에 이 도시에서 가장 수익을 많이 낼 수 있는  치킨집의 개수는 최대 M개라는 사실을 알아내었다.

도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다. 어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)이 주어진다.

둘째 줄부터 N개의 줄에는 도시의 정보가 주어진다.

도시의 정보는 0, 1, 2로 이루어져 있고, 0은 빈 칸, 1은 집, 2는 치킨집을 의미한다. 집의 개수는 2N개를 넘지 않으며, 적어도 1개는 존재한다. 치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같다.

출력

첫째 줄에 폐업시키지 않을 치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력한다.

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

public class BJ_15686 {
	static int N;
	static int M;
	static int s_cnt;
	static int result = Integer.MAX_VALUE;

	public static void powerSet(int[][] s_arr, int[][] arr, int cnt, boolean[] isSelected) {
		if (cnt == s_cnt) {
			int sum = 0;
			int set_cnt = 0;
			for (int k = 0; k < s_cnt; k++) { // isSelected를 탐색해서
				if (isSelected[k]) { // 선택된 원소일 경우
					set_cnt++;
				}
			}
			if (set_cnt <= M && set_cnt >= 1) {
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < N; j++) {
						if (arr[i][j] == 1) {
							int distance = Integer.MAX_VALUE;
							for (int k = 0; k < s_cnt; k++) { // isSelected를 탐색해서
								if (isSelected[k]) { // 선택된 원소일 경우
									int dis = 0;
									dis += i > s_arr[k][0] ? i - s_arr[k][0] : s_arr[k][0] - i;
									dis += j > s_arr[k][1] ? j - s_arr[k][1] : s_arr[k][1] - j;
									if (distance > dis)
										distance = dis;
								}
							}
							sum += distance;
						}
					}
				}
				if (result > sum)
					result = sum;
			}
			return;
		}

		isSelected[cnt] = true;
		powerSet(s_arr, arr, cnt + 1, isSelected);
		isSelected[cnt] = false;
		powerSet(s_arr, arr, cnt + 1, isSelected);
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		int[][] arr = new int[N][N];
		s_cnt = 0;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
				if (arr[i][j] == 2)
					s_cnt++;
			}
		}
		int[][] s_arr = new int[s_cnt][2];
		for (int i = 0, k = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (arr[i][j] == 2) {
					s_arr[k][0] = i;
					s_arr[k][1] = j;
					k++;
				}
			}
		}
		powerSet(s_arr, arr, 0, new boolean[s_cnt]);
		System.out.println(result);
	}
}

원소의 갯수가 1~M  사이인 부분집합을 만들어 최소 치킨거리를 계산해 주었습니다.

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

문제

캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 N×M인 격자판으로 나타낼 수 있다. 격자판은 1×1 크기의 칸으로 나누어져 있고, 각 칸에 포함된 적의 수는 최대 하나이다. 격자판의 N번행의 바로 아래(N+1번 행)의 모든 칸에는 성이 있다.

성을 적에게서 지키기 위해 궁수 3명을 배치하려고 한다. 궁수는 성이 있는 칸에 배치할 수 있고, 하나의 칸에는 최대 1명의 궁수만 있을 수 있다. 각각의 턴마다 궁수는 적 하나를 공격할 수 있고, 모든 궁수는 동시에 공격한다. 궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고, 그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다. 같은 적이 여러 궁수에게 공격당할 수 있다. 공격받은 적은 게임에서 제외된다. 궁수의 공격이 끝나면, 적이 이동한다. 적은 아래로 한 칸 이동하며, 성이 있는 칸으로 이동한 경우에는 게임에서 제외된다. 모든 적이 격자판에서 제외되면 게임이 끝난다. 

게임 설명에서 보다시피 궁수를 배치한 이후의 게임 진행은 정해져있다. 따라서, 이 게임은 궁수의 위치가 중요하다. 격자판의 상태가 주어졌을 때, 궁수의 공격으로 제거할 수 있는 적의 최대 수를 계산해보자.

격자판의 두 위치 (r1, c1), (r2, c2)의 거리는 |r1-r2| + |c1-c2|이다.

입력

첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다.

출력

첫째 줄에 궁수의 공격으로 제거할 수 있는 적의 최대 수를 출력한다.

제한

• 3 ≤ N, M ≤ 15
• 1 ≤ D ≤ 10

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class BJ_17135 {
	static int N;
	static int M;
	static int D;
	static int K = 3; // 궁수
	static int result = Integer.MIN_VALUE;

	private static void makeCombination(int[] arr, List<int[]> map, int toSelect, int[] selected, int startIdx) {
		//arr = 궁수 후보 배열, map = 적 좌표 리스트, toSelect = 뽑은 궁수의 수, selected = 뽑은 궁수 조합, startIdx = 중복방지 시작 index
		if (toSelect == K) {
			// 이번 조합에 제거할 수 있는 적의 수
			int cnt = 0;
			// 원본 보존 위해 map 복사
			List<int[]> temp_map = new ArrayList<int[]>();
			for (int[] temp : map) {
				int[] tt = Arrays.copyOf(temp, temp.length);
				temp_map.add(tt);
			}
			// temp_map 에서 적이 모두 사라질 때까지 동작
			while (temp_map.size() != 0) {
				int[] attack = new int[3];
				int[][] remove_obj = new int[K][2];
				// 세명의 궁수가 각각
				for (int j = 0; j < K; j++) {
					int near = Integer.MAX_VALUE;
					int near_i = Integer.MAX_VALUE;
					// 모든 적 에 대해;
					for (int i = 0; i < temp_map.size(); i++) {
						// 궁수와 적 거리 계산
						int dist = Math.abs(selected[j] - temp_map.get(i)[1]) + N - temp_map.get(i)[0];
						// 궁수와 적 거리가 가장 가까운 모든 적 중에서 왼쪽 원소를 찾아야 하므로 >= 으로 비교
						if (near >= dist) {
							// 최단 거리가 단축되면 최단거리가 같은 적들이 reset되므로
							// 제일 왼쪽 원소의 column을 저장하는 near_i도 reset 시켜줘야한다.
							if (near != dist)
								near_i = Integer.MAX_VALUE;
							// 최단 거리 갱신
							near = dist;
							// 거리가 사정거리이내인 것들에서
							if (near <= D) {
								// 가장 가까운 적 중에서 가장 왼쪽인 적 갱신
								if (near_i > temp_map.get(i)[1]) {
									// near_i(=가장 왼쪽 원소의 column) 갱신
									near_i = temp_map.get(i)[1];
									// 가장 왼쪽 원소의 temp_map 리스트 인덱스를 저장(중복 제거에 사용)
									attack[j] = i;
									// 가장 왼쪽 원소의 객체 저장(적 제거에 사용)
									remove_obj[j] = temp_map.get(i);
								}

							}
							// 공격할 수 있는 대상이 없으면 적제거 반복문을 돌지 않게 값 조정
							else
								attack[j] = map.size();
						}
					}
				}
				// 공격 대상 중복 제거
				// 중복되는 적이 적 제거 반복문을 돌지 않게 값 조정
				if (attack[0] == attack[1])
					attack[1] = map.size();
				if (attack[1] == attack[2])
					attack[2] = map.size();
				if (attack[0] == attack[2])
					attack[2] = map.size();
				// 궁수의 적제거
				for (int i = 0; i < K; i++) {
					// 조정한 값(=map.size())은 반복문을 돌지 않는 조건
					if (attack[i] < map.size()) {
						// 적 제거, 제거한 적의 수 ++;
						temp_map.remove(remove_obj[i]);
						cnt++;
					}
				}
				// ------------------------
				// 성벽에 닿아 제외될 적 수 count
				int rmv_cnt = 0;
				for (int i = 0; i < temp_map.size(); i++) {
					// 적 배열 아래로 한 칸씩
					temp_map.get(i)[0] += 1;
					// 성벽에 닿으면 rmv_cnt++;
					if (temp_map.get(i)[0] == N) {
						rmv_cnt++;
					}
				}
				// 제외할 적 수 만큼 remove
				// 성벽에 닿는 적은 가장 아랫줄에 있던 적들은 리스트의 가장 뒤에 저장된 요소들이므로
				// 뒤에서부터 지워주면 된다.
				for (int i = 0; i < rmv_cnt; i++) {
					temp_map.remove(temp_map.size() - 1);
				}
			}
			// 최대 제거 가능한 적의 수 갱신
			if (result < cnt)
				result = cnt;
			return;
		}
		// 조합 재귀
		for (int i = startIdx; i < arr.length; i++) {
			selected[toSelect] = arr[i];
			makeCombination(arr, map, toSelect + 1, selected, i + 1);
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		D = Integer.parseInt(st.nextToken());
		List<int[]> map = new ArrayList<int[]>();

		int[][] arr = new int[N][M];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
				if (arr[i][j] == 1) {
					int[] temp = new int[2];
					temp[0] = i;
					temp[1] = j;
					map.add(temp);
				}
			}
		}
		// 가능한 궁수의 요소들 초기화
		int[] archer = new int[M];
		for (int i = 0; i < M; i++) {
			archer[i] = i;
		}
		makeCombination(archer, map, 0, new int[K], 0);
		System.out.println(result);
	}
}

적의 좌표를 map 리스트로 받아와 궁수의 조합에 따라 게임을 진행해 최대 제거 가능한 적의 수를 갱신해 풀이해주었습니다.

최단 거리가 같으면 가장 왼쪽의 적을 제거해 주는 규칙을 구현하는 것이 까다로웠던 문제라고 생각합니다.

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

문제

동근이는 무인 경비 회사 경비원으로 항상 대기하고 있다가 호출이 들어오면 경비차를 몰고 그 곳으로 달려가야 한다. 동근이가 담당하고 있는 곳은 직사각형 모양의 블록으로 블록 중간을 가로질러 차가 통과할만한 길이 없다. 이 블록 경계에 무인 경비를 의뢰한 상점들이 있다.

예를 들어 가로의 길이가 10, 세로의 길이가 5인 블록의 경계에 무인 경비를 의뢰한 3개의 상점이 있다고 하자. <그림 1>과 같이 이들은 1, 2, 3으로 표시되어 있고, 동근이는 X로 표시한 위치에 있다.

< 그림 1 >

1번 상점에서 호출이 들어 왔을 때 동근이가 블록을 시계방향으로 돌아 이동하면 이동 거리가 12가 된다. 반면 반시계방향으로 돌아 이동하면 이동 거리는 18이 된다. 따라서 동근이가 1번 상점으로 가는 최단 거리는 12가 된다. 마찬가지로 동근이의 위치에서 2번 상점까지의 최단 거리는 6, 3번 상점까지의 최단 거리는 5가 된다.

블록의 크기와 상점의 개수 및 위치 그리고 동근이의 위치가 주어질 때 동근이의 위치와 각 상점 사이의 최단 거리의 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 블록의 가로의 길이와 세로의 길이가 차례로 주어진다. 둘째 줄에 상점의 개수가 주어진다. 블록의 가로의 길이와 세로의 길이, 상점의 개수는 모두 100이하의 자연수이다. 이어 한 줄에 하나씩 상점의 위치가 주어진다. 상점의 위치는 두 개의 자연수로 표시된다. 첫째 수는 상점이 위치한 방향을 나타내는데, 1은 블록의 북쪽, 2는 블록의 남쪽, 3은 블록의 서쪽, 4는 블록의 동쪽에 상점이 있음을 의미한다. 둘째 수는 상점이 블록의 북쪽 또는 남쪽에 위치한 경우 블록의 왼쪽 경계로부터의 거리를 나타내고, 상점이 블록의 동쪽 또는 서쪽에 위치한 경우 블록의 위쪽 경계로부터의 거리를 나타낸다. 마지막 줄에는 동근이의 위치가 상점의 위치와 같은 방식으로 주어진다. 상점의 위치나 동근이의 위치는 블록의 꼭짓점이 될 수 없다.

출력

첫째 줄에 동근이의 위치와 각 상점 사이의 최단 거리의 합을 출력한다.

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

public class BJ_02564 {
	static int N;
	static int M;
	static int cnt;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		int TC = Integer.parseInt(br.readLine());
		int[][] store = new int[TC+1][2];
		int sum = 0;
		int dong_dir = 10;
		for (int t = 0; t <= TC; t++) {
			String str = br.readLine();
			st = new StringTokenizer(str, " ");
			store[t][0] = Integer.parseInt(st.nextToken());
			store[t][1] = Integer.parseInt(st.nextToken());
			if (t == TC)
				dong_dir = store[t][0];
			switch (store[t][0]) {
			case 1:// 북
				store[t][0] = N;
				break;
			case 2:// 남
				store[t][0] = 0;
				break;
			case 3:// 서
				store[t][0] = N - store[t][1];
				store[t][1] = 0;
				break;
			case 4:// 동
				store[t][0] = N- store[t][1];
				store[t][1] = M;
				break;
			}
		}
		for (int t = 0; t < TC; t++) {
			cnt = 0;
			int[] dong = new int[2];
			dong[0] = store[TC][0];
			dong[1] = store[TC][1];
			guard(dong_dir, dong, store[t]);
			if (cnt > N + M)
				cnt = 2 * (N + M) - cnt;
			sum += cnt;
		}
		System.out.println(sum);
	}

	// 북 남 서 동
	static void guard(int dir, int[] dong, int[] store) {
		if (dong[0] == store[0] && dong[1] == store[1])
			return;
		switch (dir) {
		case 1: // 북->동 (column 이동)
			if (dong[1] == M) {
				guard(4, dong, store);
				break;
			}
			dong[1] += 1;
			cnt++;
			guard(1, dong, store);
			break;
		case 4: // 동->남
			if (dong[0] == 0) {
				guard(2, dong, store);
				break;
			}
			dong[0] -= 1;
			cnt++;
			guard(4, dong, store);
			break;
		case 2: // 남->서 (column 이동)
			if (dong[1] == 0) {
				guard(3, dong, store);
				break;
			}
			dong[1] -= 1;
			cnt++;
			guard(2, dong, store);
			break;
		case 3: // 서->북
			if (dong[0] == N) {
				guard(1, dong, store);
				break;
			}
			dong[0] += 1;
			cnt++;
			guard(3, dong, store);
			break;
		}
	}
}

상점과 동근이의 방향 및 위치를 입력받아 좌표로 바꾸어 준 뒤

시계방향으로 이동하며 상점의 좌표와 동근이의 좌표가 같아질 때 종료하는 guard 재귀함수를 작성해 주었습니다.

단 시계방향으로 진행한 거리가 최단 거리가 아닐 수 있으므로 거리가 가로+세로보다 크다면 전체 둘레에서 시계방향 진행 거리를 빼주는 방식으로 최단 거리를 계산해 주었습니다.

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

문제

매일 매일 일곱 난쟁이는 광산으로 일을 하러 간다. 난쟁이가 일을 하는 동안 백설공주는 그들을 위해 저녁 식사를 준비한다. 백설공주는 의자 일곱개, 접시 일곱개, 나이프 일곱개를 준비한다.

어느 날 광산에서 아홉 난쟁이가 돌아왔다. (왜 그리고 어떻게 아홉 난쟁이가 돌아왔는지는 아무도 모른다) 아홉 난쟁이는 각각 자신이 백설공주의 일곱 난쟁이라고 우기고 있다.

백설공주는 이런 일이 생길 것을 대비해서, 난쟁이가 쓰고 다니는 모자에 100보다 작은 양의 정수를 적어 놓았다. 사실 백설 공주는 공주가 되기 전에 매우 유명한 수학자였다. 따라서, 일곱 난쟁이의 모자에 쓰여 있는 숫자의 합이 100이 되도록 적어 놓았다.

아홉 난쟁이의 모자에 쓰여 있는 수가 주어졌을 때, 일곱 난쟁이를 찾는 프로그램을 작성하시오. (아홉 개의 수 중 합이 100이 되는 일곱 개의 수를 찾으시오)

입력

총 아홉개 줄에 1보다 크거나 같고 99보다 작거나 같은 자연수가 주어진다. 모든 숫자는 서로 다르다. 또, 항상 답이 유일한 경우만 입력으로 주어진다.

출력

일곱 난쟁이가 쓴 모자에 쓰여 있는 수를 한 줄에 하나씩 출력한다.

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

public class Main {
	static int T = 9;
	static int K = 7;

	private static void makeCombination(int[] num, int toSelect, int[] selected, int startIdx) {
		if (toSelect == K) {
			int sum = 0;
			for (int i = 0; i < T; i++) {
				if (selected[i] != 0)
					sum += selected[i];
			}
			if (sum == 100) {
				for (int j = 0; j < T; j++) {
					if (selected[j] != 0)
						System.out.println(selected[j]);
				}
			}
			return;
		}
		for (int i = startIdx; i < num.length; i++) {
			selected[toSelect] = num[i];
			makeCombination(num, toSelect + 1, selected, i + 1);
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int[] arr = new int[T];
		for (int t = 0; t < T; t++) {
			arr[t] = Integer.parseInt(br.readLine());
		}
		makeCombination(arr, 0, new int[T], 0);
	}
}

9개의 원소 중 7개로 이루어진 조합을 완성했을 때 selected 배열에는 선택된 조합을 제외하고는 0으로 초기화 되어있습니다.

따라서 selected[i]의 원소가 0이 아닌 경우에만 sum+= selected[i] 를 해주고,

해당 조합으로 계산한  sum ==100 인경우에 selected를 출력해줍니다.

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

문제

도영이는 짜파구리 요리사로 명성을 날렸었다. 이번에는 이전에 없었던 새로운 요리에 도전을 해보려고 한다.

지금 도영이의 앞에는 재료가 N개 있다. 도영이는 각 재료의 신맛 S와 쓴맛 B를 알고 있다. 여러 재료를 이용해서 요리할 때, 그 음식의 신맛은 사용한 재료의 신맛의 곱이고, 쓴맛은 합이다.

시거나 쓴 음식을 좋아하는 사람은 많지 않다. 도영이는 재료를 적절히 섞어서 요리의 신맛과 쓴맛의 차이를 작게 만들려고 한다. 또, 물을 요리라고 할 수는 없기 때문에, 재료는 적어도 하나 사용해야 한다.

재료의 신맛과 쓴맛이 주어졌을 때, 신맛과 쓴맛의 차이가 가장 작은 요리를 만드는 프로그램을 작성하시오.

입력

첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 모두 1,000,000,000보다 작은 양의 정수이다.

출력

첫째 줄에 신맛과 쓴맛의 차이가 가장 작은 요리의 차이를 출력한다. 

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

public class Main {
	static int difference =Integer.MAX_VALUE;
	static int TC;
	public static void powerSet(int[][] taste, int cnt, boolean[] isSelected) {
		if (cnt == TC) {	
			int set_cnt=0;
			for(int i = 0; i < TC; i++) {
				if(isSelected[i] ==true) set_cnt++; 
			}
			if(set_cnt != 0) {
				int differ=0;
				int sour = 1;
				int bitter = 0;
				for (int i = 0; i < TC; i++) { 	// isSelected를 탐색해서
					if (isSelected[i]) { 		// 선택된 원소일 경우
						sour *= taste[i][0];
						bitter += taste[i][1];
					}
				}
				differ= sour>bitter?sour-bitter:bitter-sour;
				if(difference > differ) difference = differ;
			}
			return;	
		}
		isSelected[cnt] = true;
		powerSet(taste, cnt + 1, isSelected);
		isSelected[cnt] = false;
		powerSet(taste, cnt + 1, isSelected);	
	}
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		TC = Integer.parseInt(br.readLine());
		int[][] taste = new int[TC][2];
		for (int t = 0; t < TC; t++) {
			String str = br.readLine();
			st = new StringTokenizer(str, " ");
			taste[t][0] =Integer.parseInt(st.nextToken());
			taste[t][1] =Integer.parseInt(st.nextToken());
		}
		powerSet(taste, 0, new boolean[TC]);
		System.out.println(difference);	
	}
}

부분집합의 원소가 무조건 한개 이상이어야 하기 때문에 부분집합이 정해지면 isSelected 배열을 이용해 원소의 갯수를 세어주고, 원소의 갯수가 0이 아닐 때에만 신맛과 쓴맛을 계산해 차이의 최솟값을 갱신해 주도록 했습니다.

if (cnt == TC) {
int set_cnt=0;
for(int i = 0; i < TC; i++) {
if(isSelected[i] ==true) set_cnt++; 
}
if(set_cnt != 0) {
int differ=0;
int sour = 1;
int bitter = 0;
for (int i = 0; i < TC; i++) {  // isSelected를 탐색해서
if (isSelected[i]) {  // 선택된 원소일 경우
sour *= taste[i][0];
bitter += taste[i][1];
}
}
differ= sour>bitter?sour-bitter:bitter-sour;
if(difference > differ) difference = differ;
}

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

[문제]

규영이와 인영이는 1에서 18까지의 수가 적힌 18장의 카드로 게임을 하고 있다.

한 번의 게임에 둘은 카드를 잘 섞어 9장씩 카드를 나눈다. 그리고 아홉 라운드에 걸쳐 게임을 진행한다.

한 라운드에는 한 장씩 카드를 낸 다음 두 사람이 낸 카드에 적힌 수를 비교해서 점수를 계산한다.

높은 수가 적힌 카드를 낸 사람은 두 카드에 적힌 수의 합만큼 점수를 얻고,

낮은 수가 적힌 카드를 낸 사람은 아무런 점수도 얻을 수 없다.

이렇게 아홉 라운드를 끝내고 총점을 따졌을 때, 총점이 더 높은 사람이 이 게임의 승자가 된다.

두 사람의 총점이 같으면 무승부이다.

이번 게임에 규영이가 받은 9장의 카드에 적힌 수가 주어진다.

규영이가 내는 카드의 순서를 고정하면, 인영이가 어떻게 카드를 내는지에 따른 9!가지 순서에 따라

규영이의 승패가 정해질 것이다.

이 때, 규영이가 이기는 경우와 지는 경우가 총 몇 가지 인지 구하는 프로그램을 작성하라.


[입력]

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

각 테스트 케이스의 첫 번째 줄에는 아홉 개의 정수가 공백으로 구분되어 주어진다.

각 정수는 1이상 18이하이며, 같은 정수는 없다.

규영이는 정수가 주어지는 순서대로 카드를 낸다고 생각하면 된다.


[출력]

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

인영이가 카드를 내는 9! 가지의 경우에 대해 규영이가 게임을 이기는 경우의 수와 게임을 지는 경우의 수를

공백 하나로 구분하여 출력한다.

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

public class Solution {
	static int T = 9;
	static int kscore=0;
	static int iscore=0;
	static int win;
	static int lose;

	private static void makePermutation(int[] Karr, int[] Iarr, int toSelect, int[] selected, boolean[] visited) {
		if (toSelect == T) {
			kscore = 0;
			iscore = 0;
			for (int i = 0; i < T; i++) {
				if (Karr[i] > Iarr[selected[i]]) {
					kscore += Karr[i] + Iarr[selected[i]];
				} else
					iscore += Karr[i] + Iarr[selected[i]];
			}
			if (kscore > iscore)
				win++;
			else
				lose++;
			return;
		}
		for (int i = 0; i < T; i++) {
			if (!visited[i]) {
				visited[i] = true;
				selected[toSelect] = i;
				makePermutation(Karr, Iarr, toSelect + 1, selected, visited);
				visited[i] = false;
			}
		}
	}

	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());
		for (int t = 1; t <= TC; t++) {
			sb.append("#" + t + " ");
			String str = br.readLine();
			st = new StringTokenizer(str, " ");
			int[] kcard = new int[T];
			for (int i = 0; i < T; i++) {
				kcard[i] = Integer.parseInt(st.nextToken());
			}
			int[] Icard = new int[T];
			for (int k = 0, i = 1; i <= 2 * T; i++) {
				int flag = 0;
				for (int j = 0; j < T; j++) {
					if (i == kcard[j])
						flag = 1;
				}
				if (flag == 0) {
					Icard[k] = i;
					k++;
				}
			}
			win = 0;
			lose = 0;
			makePermutation(kcard, Icard, 0, new int[T], new boolean[T]);
			sb.append(win + " " + lose + "\n");
		}
		System.out.println(sb);
	}
}

인영이와 규영이의 카드는 겹치지 않으므로 이중for문을 통해 규영이의 카드에 따른 인영이의 카드 배열을 저장해주었습니다. 

int[] Icard = new int[T];
for (int k = 0, i = 1; i <= 2 * T; i++) {
int flag = 0;
for (int j = 0; j < T; j++) {
if (i == kcard[j])
flag = 1;
}
if (flag == 0) {
Icard[k] = i;
k++;
}
}

인영이의 카드 내는 순서의 순열을 구하는 makePermutation 재귀 함수를 작성해 풀이해주었습니다.

순열이 정해질 때마다 규영이와 인영이의 점수를 초기화한 뒤 서로의 점수를 구해줍니다.

점수계산 후 규영이의 점수가 더 높다면 win++ 아니라면 lose ++을 해주었습니다.

if (toSelect == T) {

kscore = 0;
iscore = 0;
for (int i = 0; i < T; i++) {
if (Karr[i] > Iarr[selected[i]]) {
kscore += Karr[i] + Iarr[selected[i]];
} else
iscore += Karr[i] + Iarr[selected[i]];
}
if (kscore > iscore)
win++;
else
lose++;
return;
}

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

문제

크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 값은 4이다.

배열은 회전 연산을 수행할 수 있다. 회전 연산은 세 정수 (r, c, s)로 이루어져 있고, 가장 왼쪽 윗 칸이 (r-s, c-s), 가장 오른쪽 아랫 칸이 (r+s, c+s)인 정사각형을 시계 방향으로 한 칸씩 돌린다는 의미이다. 배열의 칸 (r, c)는 r행 c열을 의미한다.

예를 들어, 배열 A의 크기가 6×6이고, 회전 연산이 (3, 4, 2)인 경우에는 아래 그림과 같이 회전하게 된다.

회전 연산이 두 개 이상이면, 연산을 수행한 순서에 따라 최종 배열이 다르다.

다음은 배열 A의 크기가 5×6이고, 회전 연산이 (3, 4, 2), (4, 2, 1)인 경우의 예시이다.

배열 A에 (3, 4, 2), (4, 2, 1) 순서로 연산을 수행하면 배열 A의 값은 12, (4, 2, 1), (3, 4, 2) 순서로 연산을 수행하면 15 이다.

배열 A와 사용 가능한 회전 연산이 주어졌을 때, 배열 A의 값의 최솟값을 구해보자. 회전 연산은 모두 한 번씩 사용해야 하며, 순서는 임의로 정해도 된다.

입력

첫째 줄에 배열 A의 크기 N, M, 회전 연산의 개수 K가 주어진다.

둘째 줄부터 N개의 줄에 배열 A에 들어있는 수 A[i][j]가 주어지고, 다음 K개의 줄에 회전 연산의 정보 r, c, s가 주어진다.

출력

배열 A의 값의 최솟값을 출력한다.

제한

• 3 ≤ N, M ≤ 50
• 1 ≤ K ≤ 6
• 1 ≤ A[i][j] ≤ 100
• 1 ≤ s
• 1 ≤ r-s < r < r+s ≤ N
• 1 ≤ c-s < c < c+s ≤ M

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

public class Spin_4 {
	static int T;
	static int N;
	static int M;
	static int min;
	private static void makePermutation(int[][] arr, int[][] oper, int toSelect, int[] selected, boolean[] visited) {
		if (toSelect == T) {
			int[][] arr_copy = new int[arr.length][arr[0].length];
			for (int i = 0; i < arr.length; i++) {
				for (int j = 0; j < arr[0].length; j++) {
					arr_copy[i][j] = arr[i][j];
				}
			}

			for (int i = 0; i < T; i++) {
				spin(arr_copy, 0, oper[selected[i]][0], oper[selected[i]][1], oper[selected[i]][2]);
				// 각행의 합 중 최솟값 출력
				if (i == T - 1) {
					for (int n = 0; n < N; n++) {
						int sum = 0;
						for (int m = 0; m < M; m++) {
							sum += arr_copy[n][m];
						}
						if (min > sum)
							min = sum;
					}
				}
			}
			return;
		}

		for (int i = 0; i < T; i++) {
			if (!visited[i]) {
				visited[i] = true;
				selected[toSelect] = i;
				makePermutation(arr, oper, toSelect + 1, selected, visited);
				visited[i] = false;
			}
		}

	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		T = Integer.parseInt(st.nextToken());
		int[][] arr = new int[N][M];
		min = Integer.MAX_VALUE;
		for (int n = 0; n < N; n++) {
			st = new StringTokenizer(br.readLine());
			for (int m = 0; m < M; m++) {
				arr[n][m] = Integer.parseInt(st.nextToken());
			}
		}

		int[][] oper = new int[T][3];
		for (int i = 0; i < T; i++) {
			st = new StringTokenizer(br.readLine());
			oper[i][0] = Integer.parseInt(st.nextToken());
			oper[i][1] = Integer.parseInt(st.nextToken());
			oper[i][2] = Integer.parseInt(st.nextToken());
		}
		makePermutation(arr, oper, 0, new int[T], new boolean[T]);

		System.out.println(min);

	}

	static void spin(int[][] arr, int t, int R, int C, int s) { //
		if (t == s)
			return;
		int r = R - 1;
		int c = C - 1;
		// 아래쪽(왼쪽으로 한칸씩)
		int temp = arr[r + s - t][c - s + t];
		for (int j = c - s + t + 1; j <= c + s - t; j++) {
			arr[r + s - t][j - 1] = arr[r + s - t][j];
		}
		// 오른쪽(아래쪽으로 한칸씩)
		for (int j = r + s - t; j > r - s + t; j--) {
			arr[j][c + s - t] = arr[j - 1][c + s - t];
		}
		// 위쪽(오른쪽으로 한칸씩)
		for (int j = c + s - t; j > c - s + t; j--) {
			arr[r - s + t][j] = arr[r - s + t][j - 1];
		}
		// 왼쪽(위쪽으로 한칸씩)
		for (int j = r - s + t; j < r + s - t; j++) {
			arr[j][c - s + t] = arr[j + 1][c - s + t];
		}
		arr[r + s - t - 1][c - s + t] = temp;
		spin(arr, t + 1, R, C, s);
	}
}

makepermutation 함수는 순열을 구하는 함수입니다.

본 문제에서는 연산 순서를 고려해 행원소합의 최솟값을 도출해야하므로,

순열이 완성되는 시점(=종료조건에 도달했을 때)에서 해당 연산 순서로 spin을 실행해 최솟값 계산을 해주었습니다.

순열을 새로 완성할 때마다 원본 배열에서 spin을 시작해야하기 때문에 순열 완성 시마다 원본배열의 복사본인 arr_copy를 만들고, arr_copy로 spin을 수행했습니다.

private static void makePermutation(int[][] arr, int[][] oper, int toSelect, int[] selected, boolean[] visited) {
if (toSelect == T) {
int[][] arr_copy = new int[arr.length][arr[0].length];
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[0].length; j++) {
arr_copy[i][j] = arr[i][j];
}
}

for (int i = 0; i < T; i++) {
spin(arr_copy, 0, oper[selected[i]][0], oper[selected[i]][1], oper[selected[i]][2]);
// 각행의 합 중 최솟값 출력
if (i == T - 1) {
for (int n = 0; n < N; n++) {
int sum = 0;
for (int m = 0; m < M; m++) {
sum += arr_copy[n][m];
}
if (min > sum)
min = sum;
}
}
}
return;
}

spin함수는 이전에 풀이한 배열 돌리기 1의 풀이와 유사하므로 링크로 설명을 대신하겠습니다.

https://mycodingbox.tistory.com/30

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

문제

크기가 N×M인 배열이 있을 때, 배열에 연산을 R번 적용하려고 한다. 연산은 총 6가지가 있다.

1번 연산은 배열을 상하 반전시키는 연산이다.

2번 연산은 배열을 좌우 반전시키는 연산이다.

3번 연산은 오른쪽으로 90도 회전시키는 연산이다.

4번 연산은 왼쪽으로 90도 회전시키는 연산이다.

5, 6번 연산을 수행하려면 배열을 크기가 N/2×M/2인 4개의 부분 배열로 나눠야 한다. 아래 그림은 크기가 6×8인 배열을 4개의 그룹으로 나눈 것이고, 1부터 4까지의 수로 나타냈다.

5번 연산은 1번 그룹의 부분 배열을 2번 그룹 위치로, 2번을 3번으로, 3번을 4번으로, 4번을 1번으로 이동시키는 연산이다.

6번 연산은 1번 그룹의 부분 배열을 4번 그룹 위치로, 4번을 3번으로, 3번을 2번으로, 2번을 1번으로 이동시키는 연산이다.

입력

첫째 줄에 배열의 크기 N, M과 수행해야 하는 연산의 수 R이 주어진다.

둘째 줄부터 N개의 줄에 배열 A의 원소 Aij가 주어진다.

마지막 줄에는 수행해야 하는 연산이 주어진다. 연산은 공백으로 구분되어져 있고, 문제에서 설명한 연산 번호이며, 순서대로 적용시켜야 한다.

출력

입력으로 주어진 배열에 R개의 연산을 순서대로 수행한 결과를 출력한다.

제한

• 2 ≤ N, M ≤ 100
• 1 ≤ R ≤ 1,000
• N, M은 짝수
• 1 ≤ Aij ≤ 108

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

public class Main {
	static int[][] arr;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int R = Integer.parseInt(st.nextToken());

		// 배열 입력
		arr = new int[N][M];
		for (int n = 0; n < N; n++) {
			st = new StringTokenizer(br.readLine());
			for (int m = 0; m < M; m++) {
				arr[n][m] = Integer.parseInt(st.nextToken());
			}
		}
		
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < R; i++) {
			switch (Integer.parseInt(st.nextToken())) {
			case 1:
				oper_1();
				break;
			case 2:
				oper_2();
				break;
			case 3:
				oper_3();
				break;
			case 4:
				oper_4();
				break;
			case 5:
				oper_5();
				break;
			case 6:
				oper_6();
				break;
			}
		}
		for (int n = 0; n < arr.length; n++) {
			for (int m = 0; m < arr[0].length; m++) {
				if (m == arr[0].length - 1)
					System.out.print(arr[n][m]);
				else
					System.out.print(arr[n][m] + " ");
			}
			if (n != arr.length - 1)
				System.out.println();
		}

	}

	static void oper_1() {
		int temp;
		for (int n = 0; n < arr.length / 2; n++) {
			for (int j = 0; j < arr[0].length; j++) {
				temp = arr[n][j];
				arr[n][j] = arr[arr.length - 1 - n][j];
				arr[arr.length - 1 - n][j] = temp;
			}
		}
	}

	static void oper_2() {
		int temp;
		for (int n = 0; n < arr.length; n++) {
			for (int j = 0; j < arr[0].length / 2; j++) {
				temp = arr[n][j];
				arr[n][j] = arr[n][arr[0].length - 1 - j];
				arr[n][arr[0].length - 1 - j] = temp;
			}
		}
	}

	static void oper_3() {
		int[][] arr_3 = new int[arr[0].length][arr.length];

		for (int i = 0; i < arr[0].length; i++) {
			for (int j = 0; j < arr.length; j++) {
				arr_3[i][j] = arr[arr.length - 1 - j][i];
			}
		}

		arr = new int[arr[0].length][arr.length];
		for (int i = 0; i < arr_3.length; i++) {
			for (int j = 0; j < arr_3[0].length; j++) {
				arr[i][j] = arr_3[i][j];
			}
		}
	}

	static void oper_4() {
		int[][] arr_3 = new int[arr[0].length][arr.length];

		for (int i = 0; i < arr[0].length; i++) {
			for (int j = 0; j < arr.length; j++) {
				arr_3[i][j] = arr[j][arr[0].length - 1 - i];
			}
		}

		arr = new int[arr[0].length][arr.length];
		for (int i = 0; i < arr_3.length; i++) {
			for (int j = 0; j < arr_3[0].length; j++) {
				arr[i][j] = arr_3[i][j];
			}
		}
	}

	static void oper_5() {
		int[][] temp = new int[arr.length/2][arr[0].length/2];
		// 1번 부분 배열 temp에 저장
		for (int i = 0; i < arr.length/2; i++) {
			for (int j = 0; j < arr[0].length/2; j++) {
				temp[i][j] = arr[i][j];
			}
		}
		// 4->1
		for (int i = 0; i < arr.length/2; i++) {
			for (int j = 0; j < arr[0].length/2; j++) {
				arr[i][j] = arr[arr.length/2 + i][j];
			}
		}
		// 3->4
		for (int i = arr.length/2; i < arr.length; i++) {
			for (int j = 0; j < arr[0].length/2; j++) {
				arr[i][j] = arr[i][arr[0].length/2+j];
			}
		}
		// 2->3
		for (int i = arr.length/2; i < arr.length; i++) {
			for (int j = arr[0].length/2; j < arr[0].length; j++) {
				arr[i][j] = arr[i-arr.length/2][j];
			}
		}
		// 1->2
		for (int i = 0; i < arr.length/2; i++) {
			for (int j = arr[0].length/2; j < arr[0].length; j++) {
				arr[i][j] = temp[i][j-arr[0].length/2];
			}
		}
	}

	static void oper_6() {
		int[][] temp = new int[arr.length/2][arr[0].length/2];
		// 1번 부분 배열 temp에 저장
		for (int i = 0; i < arr.length/2; i++) {
			for (int j = 0; j < arr[0].length/2; j++) {
				temp[i][j] = arr[i][j];
			}
		}
		// 2->1
		for (int i = 0; i < arr.length/2; i++) {
			for (int j = 0; j < arr[0].length/2; j++) {
				arr[i][j] = arr[i][arr[0].length/2+j];
			}
		}
		// 3->2
		for (int i = 0; i < arr.length/2; i++) {
			for (int j = arr[0].length/2; j < arr[0].length; j++) {
				arr[i][j] = arr[arr.length/2+ i][j];
			}
		}
		// 4->3
		for (int i = arr.length/2; i < arr.length; i++) {
			for (int j = arr[0].length/2; j < arr[0].length; j++) {
				arr[i][j] = arr[i][j-arr[0].length/2];
			}
		}
		// 1->4
		for (int i = arr.length/2; i < arr.length; i++) {
			for (int j = 0; j < arr[0].length/2; j++) {
				arr[i][j] = temp[i-arr.length/2][j];
			}
		}
	}
}

//oper_1(상하 반전 함수)

//상단부 하단부 원소 스위칭

for (int n = 0; n < arr.length / 2; n++) {
for (int j = 0; j < arr[0].length; j++) {
temp = arr[n][j];
arr[n][j] = arr[arr.length - 1 - n][j];
arr[arr.length - 1 - n][j] = temp;
}
}

//oper_2(좌우 반전 함수)

//좌측 우측 원소 스위칭

//oper_2와 유사하므로 설명을 생략하겠습니다.

//oper_3(오른쪽으로 90도 회전)

//N*M 배열을 90도 회전한 값을 저장할 M*N 배열 arr_3을 새로 만들어 주고, 새로운 배열에 들어올 기존 값의 index를 계산해 회전한 값을 저장해줍니다.

//static 변수인 arr 배열을 M*N인 새로운 배열로 초기화 하고 arr_3의 내용을  arr에복사해줍니다.

int[][] arr_3 = new int[arr[0].length][arr.length];
for (int i = 0; i < arr[0].length; i++) {
for (int j = 0; j < arr.length; j++) {
arr_3[i][j] = arr[arr.length - 1 - j][i];
}
}
arr = new int[arr[0].length][arr.length];
for (int i = 0; i < arr_3.length; i++) {
for (int j = 0; j < arr_3[0].length; j++) {
arr[i][j] = arr_3[i][j];
}
}

//oper_4(왼쪽으로 90도 회전)

//oper_3과 유사하므로 설명을 생략하겠습니다.

//oper_5(부분 배열 시계방향 회전)

//1번 부분 배열을 temp 에 저장해준 뒤, 빈칸이 된 1번 부분배열 자리를 4번이, 

//빈칸이 된 4번 자리를 3번이, 빈칸이된 3번 자리를 2번이 차지하는 과정을 거쳐 

//마지막에 빈칸이된 2번 자리에 temp에 있던 1번 부분배열을 넣어주어 시계방향 회전을 구현했습니다.

int[][] temp = new int[arr.length/2][arr[0].length/2];
// 1번 부분 배열 temp에 저장
for (int i = 0; i < arr.length/2; i++) {
for (int j = 0; j < arr[0].length/2; j++) {
temp[i][j] = arr[i][j];
}
}
// 4->1
for (int i = 0; i < arr.length/2; i++) {
for (int j = 0; j < arr[0].length/2; j++) {
arr[i][j] = arr[arr.length/2 + i][j];
}
}
// 3->4
for (int i = arr.length/2; i < arr.length; i++) {
for (int j = 0; j < arr[0].length/2; j++) {
arr[i][j] = arr[i][arr[0].length/2+j];
}
}
// 2->3
for (int i = arr.length/2; i < arr.length; i++) {
for (int j = arr[0].length/2; j < arr[0].length; j++) {
arr[i][j] = arr[i-arr.length/2][j];
}
}
// 1->2
for (int i = 0; i < arr.length/2; i++) {
for (int j = arr[0].length/2; j < arr[0].length; j++) {
arr[i][j] = temp[i][j-arr[0].length/2];
}
}

//oper_6(부분 배열 반시계방향 회전)

//oper_5와  유사하므로 설명을 생략하겠습니다.