16637 괄호 추가하기
📌문제 링크
https://www.acmicpc.net/problem/16637
문제
길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순서대로 계산해야 한다. 예를 들어, 3+8×7-9×2의 결과는 136이다.
수식에 괄호를 추가하면, 괄호 안에 들어있는 식은 먼저 계산해야 한다. 단, 괄호 안에는 연산자가 하나만 들어 있어야 한다. 예를 들어, 3+8×7-9×2에 괄호를 3+(8×7)-(9×2)와 같이 추가했으면, 식의 결과는 41이 된다. 하지만, 중첩된 괄호는 사용할 수 없다. 즉, 3+((8×7)-9)×2, 3+((8×7)-(9×2))은 모두 괄호 안에 괄호가 있기 때문에, 올바른 식이 아니다.
수식이 주어졌을 때, 괄호를 적절히 추가해 만들 수 있는 식의 결과의 최댓값을 구하는 프로그램을 작성하시오. 추가하는 괄호 개수의 제한은 없으며, 추가하지 않아도 된다.
입력
첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 번갈아가면서 나온다. 연산자는 +, -, 중 하나이다. 여기서 는 곱하기 연산을 나타내는 × 연산이다. 항상 올바른 수식만 주어지기 때문에, N은 홀수이다.
출력
첫째 줄에 괄호를 적절히 추가해서 얻을 수 있는 결과의 최댓값을 출력한다. 정답은 231보다 작고, -231보다 크다.
💡 문제 풀이
숫자는 모두 한 자리 수이므로 입력받은 수식 문자열의 짝수 번째가 숫자이고, 괄호 안에는 연산자가 하나만 들어있으므로 괄호 안에 숫자는 2개만 들어가게 된다.
맨 마지막 숫자를 제외한 모든 숫자마다 그 다음 숫자와 괄호로 묶을지, 묶지 않을지를 선택하는 부분집합을 사용해서 풀었다.
📋코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
static int N, M;
static String expr;
static int max = Integer.MIN_VALUE;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
expr = br.readLine();
subset(0, 0);
System.out.println(max);
}
private static void subset(int cnt, int sum) {
// 부분집합이 완성됐을 때
if (cnt > N - 1) {
max = Math.max(max, sum);
return;
}
// 연산자 구하기
// 0번째 숫자라면 덧셈으로 시작
// 2번째 숫자부터 이전 연산자를 구해 sum값과 계산하기
char op = cnt == 0 ? '+' : expr.charAt(cnt - 1);
// 선택하는 경우
if (cnt < N-1) {
// 지금 숫자부터 그 다음 숫자까지 괄호로 묶음 (먼저 계산함)
int bracket = calculate(expr.charAt(cnt) - '0', expr.charAt(cnt + 2) - '0', expr.charAt(cnt + 1));
// sum값과 계산, 다음으로 고려할 숫자는 4번째 뒤 숫자
subset(cnt + 4, calculate(sum, bracket, op));
}
// 선택하지 않는 경우
subset(cnt + 2, calculate(sum, expr.charAt(cnt) - '0', op));
}
// 숫자 a와 b를 opr 연산자에 맞게 계산하는 함수
private static int calculate(int a, int b, char opr) {
int sum = a;
switch (opr) {
case '+':
sum += b;
break;
case '-':
sum -= b;
break;
case '*':
sum *= b;
}
return sum;
}
}⏱ 시간 복잡도
숫자의 개수(N/2)만큼 부분집합 : O(2^(N/2))
메모리 : 14228KB, 시간 : 128ms
17070 파이프 옮기기 1
📌문제 링크
https://www.acmicpc.net/problem/17070
문제
유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다.
오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다.
파이프는 회전시킬 수 있으며, 아래와 같이 3가지 방향이 가능하다.
파이프는 매우 무겁기 때문에, 유현이는 파이프를 밀어서 이동시키려고 한다. 벽에는 새로운 벽지를 발랐기 때문에, 파이프가 벽을 긁으면 안 된다. 즉, 파이프는 항상 빈 칸만 차지해야 한다.
파이프를 밀 수 있는 방향은 총 3가지가 있으며, →, ↘, ↓ 방향이다. 파이프는 밀면서 회전시킬 수 있다. 회전은 45도만 회전시킬 수 있으며, 미는 방향은 오른쪽, 아래, 또는 오른쪽 아래 대각선 방향이어야 한다.
파이프가 가로로 놓여진 경우에 가능한 이동 방법은 총 2가지, 세로로 놓여진 경우에는 2가지, 대각선 방향으로 놓여진 경우에는 3가지가 있다.
아래 그림은 파이프가 놓여진 방향에 따라서 이동할 수 있는 방법을 모두 나타낸 것이고, 꼭 빈 칸이어야 하는 곳은 색으로 표시되어져 있다.
⬆가로
⬆세로
⬆대각선
가장 처음에 파이프는 (1, 1)와 (1, 2)를 차지하고 있고, 방향은 가로이다. 파이프의 한쪽 끝을 (N, N)로 이동시키는 방법의 개수를 구해보자.
입력
첫째 줄에 집의 크기 N(3 ≤ N ≤ 16)이 주어진다. 둘째 줄부터 N개의 줄에는 집의 상태가 주어진다. 빈 칸은 0, 벽은 1로 주어진다. (1, 1)과 (1, 2)는 항상 빈 칸이다.
출력
첫째 줄에 파이프의 한쪽 끝을 (N, N)으로 이동시키는 방법의 수를 출력한다. 이동시킬 수 없는 경우에는 0을 출력한다. 방법의 수는 항상 1,000,000보다 작거나 같다.
💡 문제 풀이
파이프를 이동시키면 이전 위치의 끝 점이 이동한 뒤의 시작점이 된다.
따라서 끝점을 기준으로 빈 칸이어야 하는 곳을 체크하고, 이동시킨 뒤 파이프의 새로운 위치를 queue에 넣는다.
개인적으로 BFS가 편해서 BFS를 썼는데, 어차피 모든 경우의 수를 계산하니까 DFS를 써도 상관없을 것 같다.
📋코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
private static class Pos {
// 시작점과 끝점
int r1, c1, r2, c2;
public Pos(int r1, int c1, int r2, int c2) {
super();
this.r1 = r1;
this.c1 = c1;
this.r2 = r2;
this.c2 = c2;
}
// 지금 파이프가 어떤 모양인지 구하는 함수
private int whichShape() {
int shape = 0;
int rd = r2 - r1;
int cd = c2 - c1;
if (rd == 0 && cd == 1) { // 가로
shape = HOR;
} else if (rd == 1 && cd == 0) { // 세로
shape = VER;
} else if (rd == 1 && cd == 1) { // 대각선
shape = DIA;
}
return shape;
}
}
// 모양을 구분해주기 위한 상수
static final int HOR = 1;
static final int VER = 2;
static final int DIA = 3;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[][] map = new int[N][N];
StringTokenizer stk;
for (int i = 0; i < N; i++) {
stk = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(stk.nextToken());
}
}
int cnt = 0; // 경우의 수
// BFS
Queue<Pos> queue = new ArrayDeque<Pos>();
// 처음 파이프의 위치
queue.offer(new Pos(0,0,0,1));
int r1, c1, r2, c2; // 현재 위치
int er, ec; // 새로운 끝 점의 위치
int shape; // 모양
while(!queue.isEmpty()) {
Pos cur = queue.poll();
shape = cur.whichShape();
r1 = cur.r1;
c1 = cur.c1;
r2 = cur.r2;
c2 = cur.c2;
// (N,N)에 도착하면 경우의 수 증가
if (r2 == N-1 && c2 == N-1) {
cnt++;
continue;
}
// 오른쪽으로 밀기
// 세로일 때는 오른쪽으로 밀 수 없음
if (shape != VER) {
er = r2;
ec = c2 + 1;
if (ec < N && map[er][ec] == 0) {
queue.offer(new Pos(r2, c2, er, ec));
}
}
// 대각선으로 밀기
er = r2+1;
ec = c2+1;
if (er < N && ec < N &&
map[er][ec] == 0 && map[er-1][ec] == 0 && map[er][ec-1] == 0) {
queue.offer(new Pos(r2, c2, er, ec));
}
// 아래로 밀기
// 가로일 경우에는 아래로 밀 수 없음
if (shape != HOR) {
er = r2 + 1;
ec = c2;
if (er < N && map[er][ec] == 0) {
queue.offer(new Pos(r2, c2, er, ec));
}
}
}
System.out.println(cnt);
}
}⏱ 시간 복잡도
메모리 398676KB, 시간 772ms
17136 색종이 붙이기
📌문제 링크
https://www.acmicpc.net/problem/17136
문제
<그림 1>과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다.
<그림 1>
색종이를 크기가 10×10인 종이 위에 붙이려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 0 또는 1이 적혀 있다. 1이 적힌 칸은 모두 색종이로 덮여져야 한다. 색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안되고, 겹쳐도 안 된다. 또, 칸의 경계와 일치하게 붙여야 한다. 0이 적힌 칸에는 색종이가 있으면 안 된다.
종이가 주어졌을 때, 1이 적힌 모든 칸을 붙이는데 필요한 색종이의 최소 개수를 구해보자.
입력
총 10개의 줄에 종이의 각 칸에 적힌 수가 주어진다.
출력
모든 1을 덮는데 필요한 색종이의 최소 개수를 출력한다. 1을 모두 덮는 것이 불가능한 경우에는 -1을 출력한다.
💡 문제 풀이
처음에는 반복문을 돌며 크기가 큰 색종이부터 붙여가는 식으로 구현했는데, 틀렸습니다가 떴다..
반례
1 1 1 1 1 1 1 0 0 0
1 1 1 1 1 1 1 0 0 0
1 1 1 1 1 1 1 0 0 0
1 1 1 1 1 1 1 0 0 0
1 1 1 1 1 1 1 0 0 0
1 1 1 1 1 0 0 0 0 0
1 1 1 1 1 0 0 0 0 0
1 1 1 1 1 0 0 0 0 0
1 1 1 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0정답 : 5
이 반례의 경우 윗부분을 크기 5 색종이로 덮어버리면 답이 -1이 나오게 된다.
아래 부분을 5인 색종이를 채워야 올바른 답이 나온다.
따라서 1을 만나면 붙일 수 있는 모든 크기의 색종이를 각각 붙이는 경우로 나누어서 dfs로 탐색했다.
📋코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int N = 10;
static int res = 100; // 필요한 색종이의 최소 개수. 임의의 큰 값으로 초기화
static int[] num = { 0, 5, 5, 5, 5, 5 }; // 크기별 색종이의 남아있는 개수
static int[][] map = new int[N][N];
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stk;
int cnt = 0; // 1의 개수
for (int i = 0; i < N; i++) {
stk = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(stk.nextToken());
if (map[i][j] == 1)
cnt++;
}
}
// 1이 없으면 0 출력 후 종료
if (cnt == 0) {
System.out.println(0);
return;
}
// 색종이 붙이기
paper(cnt, 0);
if (res == 100) // 모두 덮는 것이 불가능한 경우
System.out.println(-1);
else
System.out.println(res);
}
// cnt : 남아있는 1의 개수, use : 지금까지 붙인 색종이의 개수
private static void paper(int cnt, int use) {
// 이미 구한 최소값보다 많은 종이를 사용한 경우 종료 (가지치기)
if (res < use)
return;
// 1을 모두 덮었다면 최소값 갱신 후 종료
if (cnt == 0) {
res = Math.min(res, use);
return;
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (map[i][j] == 0) continue;
// 1을 만나면 가능한 모든 크기의 종이를 붙인다.
for (int size = 1; size < 6; size++) {
if (i + size <= N && j + size <= N) {
if (num[size] > 0 && check(i, j, size)) {
// 덮는 경우
fill(i, j, size, 0);
num[size]--; // 색종이 하나 사용
paper(cnt - (size * size), use + 1);
// 덮지 않는 경우
fill(i, j, size, 1);
num[size]++;
}
}
}
return;
}
}
}
// map 채우기
private static void fill(int sr, int sc, int size, int value) {
for (int i = sr; i < sr + size; i++) {
for (int j = sc; j < sc + size; j++) {
map[i][j] = value;
}
}
}
// size 크기의 색종이를 붙이는 게 가능한지 판별하는 함수
private static boolean check(int sr, int sc, int size) {
// 색종이 크기만큼 전부 1인지 체크
for (int i = sr; i < sr + size; i++) {
for (int j = sc; j < sc + size; j++) {
if (map[i][j] == 0)
return false;
}
}
return true;
}
}⏱ 시간 복잡도
메모리 21796KB, 시간 352ms
17281 ⚾
📌문제 링크
https://www.acmicpc.net/problem/17281
문제
⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종료되고, 두 팀이 공격과 수비를 서로 바꾼다.
두 팀은 경기가 시작하기 전까지 타순(타자가 타석에 서는 순서)을 정해야 하고, 경기 중에는 타순을 변경할 수 없다. 9번 타자까지 공을 쳤는데 3아웃이 발생하지 않은 상태면 이닝은 끝나지 않고, 1번 타자가 다시 타석에 선다. 타순은 이닝이 변경되어도 순서를 유지해야 한다. 예를 들어, 2이닝에 6번 타자가 마지막 타자였다면, 3이닝은 7번 타자부터 타석에 선다.
공격은 투수가 던진 공을 타석에 있는 타자가 치는 것이다. 공격 팀의 선수가 1루, 2루, 3루를 거쳐서 홈에 도착하면 1점을 득점한다. 타자가 홈에 도착하지 못하고 1루, 2루, 3루 중 하나에 머물러있을 수 있다. 루에 있는 선수를 주자라고 한다. 이닝이 시작될 때는 주자는 없다.
타자가 공을 쳐서 얻을 수 있는 결과는 안타, 2루타, 3루타, 홈런, 아웃 중 하나이다. 각각이 발생했을 때, 벌어지는 일은 다음과 같다.
- 안타: 타자와 모든 주자가 한 루씩 진루한다.
- 2루타: 타자와 모든 주자가 두 루씩 진루한다.
- 3루타: 타자와 모든 주자가 세 루씩 진루한다.
- 홈런: 타자와 모든 주자가 홈까지 진루한다.
- 아웃: 모든 주자는 진루하지 못하고, 공격 팀에 아웃이 하나 증가한다.
한 야구팀의 감독 아인타는 타순을 정하려고 한다. 아인타 팀의 선수는 총 9명이 있고, 1번부터 9번까지 번호가 매겨져 있다. 아인타는 자신이 가장 좋아하는 선수인 1번 선수를 4번 타자로 미리 결정했다. 이제 다른 선수의 타순을 모두 결정해야 한다. 아인타는 각 선수가 각 이닝에서 어떤 결과를 얻는지 미리 알고 있다. 가장 많은 득점을 하는 타순을 찾고, 그 때의 득점을 구해보자.
입력
첫째 줄에 이닝 수 N(2 ≤ N ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에는 각 선수가 각 이닝에서 얻는 결과가 1번 이닝부터 N번 이닝까지 순서대로 주어진다. 이닝에서 얻는 결과는 9개의 정수가 공백으로 구분되어져 있다. 각 결과가 의미하는 정수는 다음과 같다.
- 안타: 1
- 2루타: 2
- 3루타: 3
- 홈런: 4
- 아웃: 0
각 이닝에는 아웃을 기록하는 타자가 적어도 한 명 존재한다.
출력
아인타팀이 얻을 수 있는 최대 점수를 출력한다.
💡 문제 풀이
4번타자로 고정된 1번 선수를 제외하고 순열을 구한 뒤 최대 점수를 시뮬레이션으로 구한다.
순열은 시간초과를 막기 위해 next permutation으로 구했다.
📋코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int N;
static int[][] hitters; // 선수들의 이닝별 결과
static int[] order; // 타순
static int maxScore; // 최대 점수
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
hitters = new int[N][9];
StringTokenizer stk;
for (int i = 0; i < N; i++) {
stk = new StringTokenizer(br.readLine());
for (int j = 0; j < 9; j++) {
hitters[i][j] = Integer.parseInt(stk.nextToken());
}
}
// 1번 선수(코드에서는 0번)를 제외하고 순열 구하기
order = new int[8];
for (int i = 0; i < 8; i++) {
order[i] = i + 1;
}
// next permutation
do {
simulate();
} while (np());
System.out.println(maxScore);
}
private static void simulate() {
Queue<Integer> queue = new ArrayDeque<>();
for (int i = 0; i < 9; i++) {
// 4번타자는 1번선수
if (i == 3) {
queue.offer(0);
continue;
}
if (i > 3) {
queue.offer(order[i-1]);
} else queue.offer(order[i]);
}
// 이닝별 득점
int score = 0;
int cur, hit; // 현재 타자 번호, 공을 치고 난 결과
int out = 0;
int[] field; // 1루, 2루, 3루, 홈에 있는 선수 기록
for (int i = 0; i < N; i++) {
out = 0;
field = new int[4];
// 1: 안타, 2: 2루타, 3: 3루타, 4: 홈런, 4: 아웃
while (true) {
cur = queue.poll();
hit = hitters[i][cur];
if (hit == 0) {
out++;
} else {
boolean flag = true;
for (int j = 0; j < 4; j++) {
// 홈에 있는 선수 계산
if (flag && field[j] == 0) {
field[j] = hit;
flag = false;
}
// 1루, 2루, 3루에 있는 선수 계산
else if (field[j] > 0) field[j] += hit;
// 홈으로 돌아올 경우 득점
if (field[j] > 3) {
score++;
field[j] = 0;
}
}
}
// 뒷 순서로 이동
queue.offer(cur);
// 아웃이 3개인 경우 이닝 종료
if (out == 3) break;
}
}
// 최댓값 갱신
maxScore = Math.max(maxScore, score);
}
// next permutation
private static boolean np() {
int n = 8;
int i = n - 1;
while (i > 0 && order[i - 1] >= order[i])
i--;
if (i == 0)
return false;
int j = n - 1;
while (order[i - 1] >= order[j])
j--;
swap(i - 1, j);
int k = n - 1;
while (i < k) {
swap(i++, k--);
}
return true;
}
private static void swap(int i, int j) {
int tmp = order[i];
order[i] = order[j];
order[j] = tmp;
}
}⏱ 시간 복잡도
메모리 84404KB, 시간 744ms
