모든 수가 0 또는 1로 이루어진 2차원 배열 a가 주어질 때, 2차원 배열 b의 경우의 수를 (10^7+ 19)로 나눈 나머지를 구하는 문제이다.
문제 조건
b의 모든 원소는 0 또는 1이며 a와 b의 크기가 같다
a의 i번째 열과 b의 i번째 열에 들어 있는 1의 개수가 같다.
b의 각 행에 들어 있는 1의 개수가 짝수이다. (0도 짝수)
일단... 경우의 수를 ~~로 나눈 나머지를 구하라고 했으니 이 수가 엄청나게 클 것이고 그냥 구하면 시간 초과가 날 것이라는 것을 알 수 있다.
대개 이렇게 결과값의 나머지를 구하라는 문제는 dp로 푸는데, dp를 어떻게 적용하면 좋을지 생각해 봤다.
dp[i][j]: (0, 0) ~ (i, j)까지 조건에 맞는 b를 만들 수 있는 경우의 수라고 정의하자.
만약 행들 중 1의 개수가 짝수이면 1을 더하면 홀수가 될 것이고, 홀수이면 1을 더하면 짝수개가 될 것이다.
열 하나를 추가해서 새롭게 만들어지는 배열은 몇 개의 짝수행을 가지고 있을 것인가. 그리고 만들 수 있는 경우의 수는 어떻게 될까.
기존에 가지고 있던 짝수행의 개수는 num개 였고 k개의 행에 1을 추가한다고 했기 때문에 k개의 행이 홀수행이 될 것이고 남은num-k개가 여전히 짝수행일 것이다. 이 경우의 수는 기존 짝수행의 개수num개 중k개를 넣을 것이기 때문에 조합(num)C(k)이다.
기존에 가지고 있던 홀수행은 n-num개(전체 배열의 행 크기 - 짝수 행 크기) 일 것이다. 조건 2에 의해 입력배열에서 column+1 열의 1의 개수를 알 수 있고 이를 oneCnt라 하자. oneCnt 중 k개는 짝수행에 넣을 것이고 남은 oneCnt - k개의 1을 홀수행에 넣을 것이다. 따라서oneCnt-k개가 짝수행이 될 것이다. 이 경우의 수는 기존 홀수행의 개수n-num개 중oneCnt - k개를 넣을 것이기 때문에 조합(n-num)C(oneCnt-k)가 될 것이다.
위와 같이 짝수행, 홀수행의 경우를 독립사건으로 보고 각자의 경우의 수를 구했으면 두 경우의 수를 곱한 결과에dp[column][num]을 곱한 결과가 우리가 구하고자 하는 dp[column+1][(num-k) + (oneCnt-k)] 값이 된다.
문자열 형태의 숫자와, +, - 가 들어있는 배열의 계산 결과 중 최댓값을 구하는 문제이다
모든 경우에 대해 구하되, 구한 값을 어딘가 저장해 두어야 한다. => dp
dp[i][j]: 인덱스 i ~ j 까지 괄호 계산을 한 값이라고 정의하자.
이때, 양수 연산의 경우 뒤에 있는 값이 최대한 커야하고, 음수 연산의 경우 뒤에 있는 값이 최대한 작아야 최댓값을 구할 수 있다.
따라서 양수 연산이 앞에 있을 땐 dp에 최댓값을, 음수 연산이 앞에 있을 땐 dp에 최솟값을 저장하도록 한다.
class Solution {
public int solution(String arr[]) {
int n = arr.length;
int[][] dp = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dp[i][j] = Integer.MIN_VALUE;
}
if (i % 2 == 0) {
dp[i][i] = Integer.parseInt(arr[i]);
}
}
return calculateItoJ(arr, dp, 0, n - 1);
}
public static int calculateItoJ(String[] arr, int[][] dp, int i, int j) { // i부터 j까지 연산
if (dp[i][j] != Integer.MIN_VALUE) {
return dp[i][j];
}
if (i - 1 >= 1 && arr[i - 1].equals("-")) { // - 연산 처리: 뒷부분이 최소가 되어야
int result = Integer.MAX_VALUE;
for (int k = i; k < j; k += 2) {
int subResult = calculate(calculateItoJ(arr, dp, i, k), arr[k + 1], calculateItoJ(arr, dp, k + 2, j));
result = Math.min(result, subResult);
}
dp[i][j] = result;
} else { // + 연산 처리: 뒷부분이 최대가 되어야
int result = Integer.MIN_VALUE;
for (int k = i; k < j; k += 2) {
int subResult = calculate(calculateItoJ(arr, dp, i, k), arr[k + 1], calculateItoJ(arr, dp, k + 2, j));
result = Math.max(result, subResult);
}
dp[i][j] = result;
}
return dp[i][j];
}
public static int calculate(int a, String op, int b) {
if (op.equals("-")) {
return a - b;
}
if (op.equals("+")) {
return a + b;
}
return 0;
}
}
적은 수의 순열부터 구한 다음에 min 값이 업데이트 되면 그 뒤는 계산하지 않도록 한다.
import java.util.*;
class Solution {
public static int min = Integer.MAX_VALUE;
public int solution(int n, int[] weak, int[] dist) {
boolean[] isVisited = new boolean[dist.length];
int[] output = new int[dist.length];
for (int i = 1; i <= n; i++) {
permutation(dist, output, isVisited, 0, n, i, weak);
if (min != Integer.MAX_VALUE) {
break;
}
}
if (min == Integer.MAX_VALUE) {
min = -1;
}
return min;
}
public static void permutation(int[] dist, int[] output, boolean[] visited, int depth, int n, int r, int[] weak) {
int length = dist.length;
if (min < r) {
return;
}
if (depth == r) {
if (isPossible(output, n, r, weak)) {
min = Math.min(min, r);
}
return;
}
for (int i = 0; i < length; i++) {
if (visited[i] != true) {
visited[i] = true;
output[depth] = dist[i];
permutation(dist, output, visited, depth + 1, n, r, weak);
visited[i] = false;
}
}
}
public static boolean isPossible(int[] output, int n, int r, int[] weak) {
if (min <= r) {
return true;
}
int length = weak.length;
for (int start = 0; start < length; start++) {
int userIndex = 0;
int before = weak[start];
boolean possibleUnit = true;
for (int i = start; i < start + length; i++) {
int now = weak[i % length];
if (i >= length) {
now += n;
}
if (now - before > output[userIndex]) {
userIndex++;
before = now;
}
if (userIndex >= r) {
possibleUnit = false;
break;
}
}
if (possibleUnit) {
return true;
}
}
return false;
}
}
(1, 0)에서 위쪽으로 기둥을 하나 설치 후, (1, 1)에서 오른쪽으로 보를 하나 만듭니다.
(2, 1)에서 위쪽으로 기둥을 하나 설치 후, (2, 2)에서 오른쪽으로 보를 하나 만듭니다.
(5, 0)에서 위쪽으로 기둥을 하나 설치 후, (5, 1)에서 위쪽으로 기둥을 하나 더 설치합니다.
(4, 2)에서 오른쪽으로 보를 설치 후, (3, 2)에서 오른쪽으로 보를 설치합니다.
만약 (4, 2)에서 오른쪽으로 보를 먼저 설치하지 않고, (3, 2)에서 오른쪽으로 보를 설치하려 한다면 2번 규칙에 맞지 않으므로 설치가 되지 않습니다.
기둥과 보를 삭제하는 기능도 있는데 기둥과 보를 삭제한 후에 남은 기둥과 보들 또한 위 규칙을 만족해야 한다.
만약, 작업을 수행한 결과가 조건을 만족하지 않는다면 해당 작업은 무시된다.
어떻게 풀지 생각해 보다가 구조물을 추가할 수 있는지 여부를 보는 함수 addValid을 만들어 두고,
구조물을 제거할 때에는 구조물을 일단 제거한 뒤, 주위에 있는 기둥과 보를 다시 추가할 때 조건에 맞는지 여부를 addValid를 이용해서 보도록 했다.
이렇게 풀면 조건에 대해 세세하게 생각할 필요 없이 addValid 함수만 호출하면 되어서 쉽게 문제를 풀 수 있다.
import java.util.*;
class Solution {
public static int HORIZONTAL = 1;
public static int VERTICAL = 0;
public static int ADD = 1;
public static int DELETE = 0;
public int[][] solution(int n, int[][] build_frame) {
TreeSet<Structure> set = new TreeSet<Structure>();
for (int i = 0; i < build_frame.length; i++) {
int x = build_frame[i][0];
int y = build_frame[i][1];
boolean isVertical = build_frame[i][2] == VERTICAL ? true : false;
boolean isAdd = build_frame[i][3] == ADD ? true : false;
if (!isAdd) {
removeValid(x, y, isVertical, set);
} else {
addValid(x, y, isVertical, set);
}
}
int[][] answer = new int[set.size()][3];
int index = 0;
for (Structure s : set) {
answer[index][0] = s.x;
answer[index][1] = s.y;
answer[index][2] = s.structure;
index++;
}
return answer;
}
public void removeValid(int x, int y, boolean isVertical, TreeSet<Structure> set) {
if (isVertical) { // 기둥
if (set.contains(new Structure(x, y + 1, VERTICAL))) {
// 제거할 기둥 위에 기둥이 있는 경우
set.remove(new Structure(x, y, VERTICAL));
if (!addValid(x, y + 1, true, set)) {
set.add(new Structure(x, y, VERTICAL));
return;
}
}
if (set.contains(new Structure(x, y + 1, HORIZONTAL))) {
// 기둥 위에 오른쪽 보가 지탱이 안되는 경우
set.remove(new Structure(x, y, VERTICAL));
if (!addValid(x, y + 1, false, set)) {
set.add(new Structure(x, y, VERTICAL));
return;
}
}
if (set.contains(new Structure(x - 1, y + 1, HORIZONTAL))) {
// 기둥 위에 왼쪽 보가 지탱이 안되는 경우
set.remove(new Structure(x, y, VERTICAL));
if (!addValid(x - 1, y + 1, false, set)) {
set.add(new Structure(x, y, VERTICAL));
return;
}
}
set.remove(new Structure(x, y, VERTICAL));
return;
}
// 보
if (set.contains(new Structure(x, y, VERTICAL))) {
// 보 위에 기둥이 있는 경우
set.remove(new Structure(x, y, HORIZONTAL));
if (!addValid(x, y, true, set)) {
set.add(new Structure(x, y, HORIZONTAL));
return;
}
}
if (set.contains(new Structure(x + 1, y, VERTICAL))) {
// 보 오른쪽 위에 기둥이 있는 경우
set.remove(new Structure(x, y, HORIZONTAL));
if (!addValid(x + 1, y, true, set)) {
set.add(new Structure(x, y, HORIZONTAL));
return;
}
}
if (set.contains(new Structure(x + 1, y, HORIZONTAL))) {
// 오른쪽 보와 연결되어있는 보에 기둥이 없는 경우
set.remove(new Structure(x, y, HORIZONTAL));
if (!addValid(x + 1, y, false, set)) {
set.add(new Structure(x, y, HORIZONTAL));
return;
}
}
if (set.contains(new Structure(x - 1, y, HORIZONTAL))) {
// 왼쪽 보와 연결되어있는 보에 기둥이 없는 경우
set.remove(new Structure(x, y, HORIZONTAL));
if (!addValid(x - 1, y, false, set)) {
set.add(new Structure(x, y, HORIZONTAL));
return;
}
}
set.remove(new Structure(x, y, HORIZONTAL));
return;
}
public boolean addValid(int x, int y, boolean isVertical, TreeSet<Structure> set) {
if (isVertical) { // 기둥
if (y == 0) {
// 바닥 위에 있는 경우
set.add(new Structure(x, y, VERTICAL));
return true;
}
if (set.contains(new Structure(x - 1, y, HORIZONTAL)) || set.contains(new Structure(x, y, HORIZONTAL))) {
// 보의 한쪽 끝 부분 위에 있는 경우
set.add(new Structure(x, y, VERTICAL));
return true;
}
if (set.contains(new Structure(x, y - 1, VERTICAL))) {
// 다른 기둥 위에 있는 경우
set.add(new Structure(x, y, VERTICAL));
return true;
}
return false;
}
// 보
if (set.contains(new Structure(x + 1, y, HORIZONTAL)) && set.contains(new Structure(x - 1, y, HORIZONTAL))) {
// 양쪽 끝 부분이 다른 보와 동시에 연결
set.add(new Structure(x, y, HORIZONTAL));
return true;
}
if (set.contains(new Structure(x, y - 1, VERTICAL)) || set.contains(new Structure(x + 1, y - 1, VERTICAL))) {
// 한쪽 끝 부분이 기둥 위에 있는 경우
set.add(new Structure(x, y, HORIZONTAL));
return true;
}
return false;
}
}
class Structure implements Comparable<Structure> {
int x, y;
int structure;
public Structure(int x, int y, int structure) {
this.x = x;
this.y = y;
this.structure = structure;
}
@Override
public int compareTo(Structure o) {
if (x == o.x) {
if (y == o.y) {
return Integer.compare(structure, o.structure);
}
return Integer.compare(y, o.y);
}
return Integer.compare(x, o.x);
}
@Override
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (!(o instanceof Structure)) {
return false;
}
Structure s = (Structure) o;
return x == s.x && y == s.y && structure == s.structure;
}
@Override
public int hashCode() {
return Objects.hash(x, y, structure);
}
@Override
public String toString() {
if (structure == 1) {
return "(" + x + ", " + y + ") 보";
}
return "(" + x + ", " + y + ") 기둥";
}
}
