천천히 빛나는
백준 : DAY 2 (Java) 본문
본 포스팅에서는 [Z, 드래곤커브, 외판원순회, 월드컵, 야구공, 빵집]을 다룹니다.
1074. (실버 1) Z
import java.io.*;
import java.util.*;
public class Main {
static int N, r, c, sz, ans;
static int map[][];
static boolean success;
static void makeZ(int x, int y, int size) {
if (size == 1)
return;
if (x < size / 2 && y < size / 2) { // 왼쪽 상단
// 앞에서 방문하지 않았음
makeZ(x, y, size / 2);
} else if (x < size / 2 && y > (size / 2) - 1) { // 오른쪽 상단
ans += size * size / 4;
makeZ(x, y - size /2, size / 2);
} else if (x > (size / 2) - 1 && y < size / 2) { // 왼쪽 하단
ans += (size * size / 4) * 2;
makeZ(x - size /2, y, size / 2);
} else { // 오른쪽 하단
ans += (size * size / 4) * 3;
makeZ(x - size /2, y - size /2, size / 2);
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
sz = (int) Math.pow(2, N);
r = Integer.parseInt(st.nextToken());
c = Integer.parseInt(st.nextToken());
makeZ(r, c, sz);
System.out.println(ans);
}
}계속 Z를 그려나가는 문제였다. 사실 이 문제는 답을 보고 풀어서 다시 복습하기 위해 작성하게 되었다. 처음에는 맵을 계속 반으로 나누는 방식으로 했었다. 하지만 시간초과가 발생했다. 그래서 계속 반씩 쪼개는 방법이 아니라 그 위치를 찾는 방식으로 수정해주었다.
배열을 사분면으로 나누고, 입력받은 r, c가 몇번째 사분면에 속하는지 찾는 방식이다.
1. r과 c가 왼쪽 상단에 속한다면 지금 앞에 있는 값이 없게 된다.
2. r과 c가 오른쪽 상단에 속한다면, 앞에 2^N-1*2^N-1 만큼은 지나쳐온 것이 된다.
3. r과 c가 오른쪽 하단에 속한다면, 오른쪽 상단의 2배만큼 지나쳐온 것이 된다.
4. r과 c가 오른쪽 하단에 속한다면, 그거의 3배를 지나쳐 온것이 된다.
처음에 (size * size / 4 ) * 2가 size * size / 2랑 똑같아서 이렇게 적었다가 틀렸습니다가 떴다. double형 타입의 문제로 보였다. double 형 타입을 써서 연산을 할 때는 식 굳이 안줄이고 직관적으로 써야겠다는 생각을 했다.
15685. (골드 3) 드래곤 커브
import java.io.*;
import java.util.*;
public class Main {
static int N;
static final int dx[] = { 0, -1, 0, 1 };
static final int dy[] = { 1, 0, -1, 0 };
static boolean map[][] = new boolean[101][101];
static ArrayList<Integer> direction;
static void direction(int d, int g) {
direction = new ArrayList<>();
direction.add(d);
while (g-- > 0) {
for (int i = direction.size() - 1; i > -1; i--) {
int di = (direction.get(i) + 1) % 4;
direction.add(di);
}
}
}
static void drawDragon(int x, int y) {
map[x][y] = true;
for(int i = 0; i < direction.size(); i++) {
int nx = x + dx[direction.get(i)];
int ny = y + dy[direction.get(i)];
map[nx][ny] = true;
x = nx;
y = ny;
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
for (int i = 0; i < N; i++) {
int x, y, d, g;
st = new StringTokenizer(br.readLine());
y = Integer.parseInt(st.nextToken());
x = Integer.parseInt(st.nextToken());
d = Integer.parseInt(st.nextToken());
g = Integer.parseInt(st.nextToken()); // 세대
direction(d, g);
drawDragon(x, y);
}
int cnt = 0;
for(int i = 0; i < 100; i++) {
for(int j = 0; j < 100; j++) {
if(map[i][j] && map[i + 1][j] && map[i][j + 1] && map[i + 1][j + 1])
cnt++;
}
}
System.out.println(cnt);
}
}뒤에서부터 90도 회전한 값이 붙게 된다는 규칙만 알게되면 아주 쉬운 문제였다. ArrayList를 만들어서 붙여주는 방식을 사용했다. 또 방향 list가 있으니 처음부터 쭉 돌면서 회전해주면 쉽게 구할 수 있었다.
10971. (실버 2) 외판원 순회 2
순열로 직접 최적의 경로를 구해도 된다. (전체 탐색하기) 하지만 다른 방법이 있는 것을 알게 되어 이에 대해 작성해보고자 한다.
import java.io.*;
import java.util.*;
public class Main {
static int N;
static int[][] W;
static int dp[][];
static final int INF = 1000000000;
static int tsp(int now, int v) {
if (v == (1 << N) - 1) {
// 방문 다했음
if (W[now][0] == 0)
return INF;
return W[now][0];
}
if (dp[now][v] != 0) { // 메모이제이션 되어있음
return dp[now][v];
}
dp[now][v] = INF;
for (int i = 0; i < N; i++) {
// 방문 안했고 들릴 수 있음
if (((v & (1 << i)) == 0) && W[now][i] != 0) {
dp[now][v] = Math.min(dp[now][v], tsp(i, v | (1 << i)) + W[now][i]);
}
}
return dp[now][v];
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
W = new int[N][N];
dp = new int[N][1 << N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
W[i][j] = Integer.parseInt(st.nextToken());
}
}
System.out.println(tsp(0, 1));
}
}DP를 이용한 방식이다. 재귀를 통해서 마지막이 5인 경우부터 최소 경로를 찾는다.
dp[v][now]는 현재 v인 상태에서 현재 값이 now일 때 도착지점까지 걸리는 최소값이다.
1. 마지막이 5인 경우 5에서 0으로 돌아오는 가중치 값이 모두 방문한 상태에서 현재 5에서 할 수 있는 선택은 시작점인 0으로 돌아가는 경우이다.
2. 1, 2, 3, 4를 방문했고 현재 4인 상태라면 5를 들렸다가 0을 가는 것이 최소값이 된다. 즉 v | (1 << i) 로 5로 간다고 표시하고 자신의 값을 추가해주는 것이다.
3. 1, 2,3을 방문한 상태라면 4, 5, 0으로 가거나 5, 4, 0으로 가는 방식이 있다. 이런 방식으로 계속 재귀를 돌게 되는데 겹치는 부분이 존재하기 때문에 시간 절약을 할 수 있다.
https://maivve.tistory.com/306
(JAVA) 백준 2098번 : 외판원 순회 --- [DP, TSP, 비트마스크]
https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수
maivve.tistory.com
이 티스토리 그림이 많은 도움이 되었다.
6987. (골드4) 월드컵
import java.io.*;
import java.util.*;
public class Main {
static int[][] game;
static int[][] matches; // A-BCDEF / B-CDEF ... 저장
static boolean isPossible;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
int tc = 4;
int size = 0;
for (int i = 1; i < 6; i++) {
size += i; // 이 경우는 15번
}
matches = new int[size][2];
int index = 0;
for (int i = 0; i < 5; i++) {
for (int j = i + 1; j < 6; j++) {
matches[index][0] = i; // 첫번째 팀
matches[index][1] = j; // 두번째 팀
index++;
}
}
while (tc-- > 0) {
st = new StringTokenizer(br.readLine());
game = new int[6][3];
isPossible = true;
for (int i = 0; i < 6; i++) {
int win = Integer.parseInt(st.nextToken());
int draw = Integer.parseInt(st.nextToken());
int lose = Integer.parseInt(st.nextToken());
if (win + draw + lose != 5) { // 한 팀당 경기수가 5가 넘을 경우
isPossible = false;
break;
}
game[i][0] = win;
game[i][1] = draw;
game[i][2] = lose;
}
if (!isPossible) {
sb.append("0 ");
} else {
isPossible = false;
gameStart(0);
if (isPossible) {
sb.append("1 ");
} else {
sb.append("0 ");
}
}
}
System.out.print(sb.toString());
}
static void gameStart(int round) {
if (isPossible)
return;
if (round == 15) { // 유효한 경기 결과
isPossible = true;
return;
}
int team1 = matches[round][0];
int team2 = matches[round][1];
if (game[team1][0] > 0 && game[team2][2] > 0) { // t1: 승 / t2: 패
game[team1][0]--;
game[team2][2]--;
gameStart(round + 1);
game[team1][0]++;
game[team2][2]++; // 다시 돌려놓고 다음 경우 실행
}
if (game[team1][1] > 0 && game[team2][1] > 0) { // t1: 무 / t2: 무
game[team1][1]--;
game[team2][1]--;
gameStart(round + 1);
game[team1][1]++;
game[team2][1]++;
}
if (game[team1][2] > 0 && game[team2][0] > 0) { // t1: 패 / t2: 승
game[team1][2]--;
game[team2][0]--;
gameStart(round + 1);
game[team1][2]++;
game[team2][0]++;
}
}
}
처음엔 모든 반례를 다 찾으려고 했었다. 계속 답이 틀리길래 결국 답을 참고했다. A-B, A-C, A-D,... D-F, E-F까지 모든 경우에 대해서 각 팀의 승, 무, 패를 결정하고 마지막 E-F까지 완성이 되는지 확인하는 것이다.
처음으로 A-B를 확인하게 된다. A-B가 승, 패 했다고 설정하고 A-C로 넘어간다. A-C도 승, 패 했다고 결정하고 쭉 내려가다보면 어느순간 숫자가 맞지 않는 부분이 생기게 될 것이다. 그럼 그 경우는 아니게 된다.
이런 식으로 15개에 대해서 누가 이기고 누가 졌는지, 혹은 비겼는지를 결정해주고 마지막까지 도달한다면 true로 설정한다. 아닐 경우는 false로 남아있게 될 것이다.
17281. (골드4) ⚾
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int N;
static int order[] = new int[9];
static boolean visited[];
static int ability[][];
static int baseball[];
static int maxScore;
static void perm(int cnt) {
if (cnt == 9) {
int score = playGame();
maxScore = Math.max(maxScore, score);
return;
}
if (cnt == 3) {
order[3] = 1; // 4번째엔 1번 타자
perm(cnt + 1);
return;
}
for (int i = 1; i < 10; i++) {
if (!visited[i]) {
order[cnt] = i;
visited[i] = true;
perm(cnt + 1);
visited[i] = false;
}
}
}
static int playGame() {
int nowOrder = 0;
int score = 0;
for (int e = 0; e < N; e++) {
int out = 0;
baseball = new int[4];
while (out != 3) {
int player = order[nowOrder];
nowOrder = (nowOrder + 1) % 9;
baseball[0] = player;
switch (ability[e][player]) {
case 0:
out++;
break;
case 1:
if (baseball[3] > 0) {
baseball[3] = 0;
score++;
}
for (int b = 3; b > 0; b--) {
baseball[b] = baseball[b - 1];
}
break;
case 2:
for (int b = 3; b > 1; b--) {
if (baseball[b] > 0) {
baseball[b] = 0;
score++;
}
}
for (int b = 3; b > 1; b--) {
baseball[b] = baseball[b - 2];
baseball[b - 2] = 0;
}
break;
case 3:
for (int b = 3; b > 0; b--) {
if (baseball[b] > 0) {
baseball[b] = 0;
score++;
}
}
for (int b = 3; b > 2; b--) {
baseball[b] = baseball[b - 3];
baseball[b - 3] = 0;
}
break;
case 4:
for (int b = 3; b > -1; b--) {
if (baseball[b] > 0) {
baseball[b] = 0;
score++;
}
}
break;
}
}
}
return score;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
visited = new boolean[10];
visited[1] = true;
ability = new int[N][10];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 1; j < 10; j++) {
ability[i][j] = Integer.parseInt(st.nextToken());
}
}
perm(0);
System.out.println(maxScore);
}
}하나하나 구현해준 방식이다. 내용만 잘 따라가면 구현 자체는 어렵지 않았다. 나는 504ms가 나왔는데 비트마스킹으로 푸는 경우 좀 더 빠른 것 같아서 비트마스킹 내용을 추가로 정리하고자 한다. 내 코드에서는 0이 타석, 1이 1루, 2가 2루, 3이 3루이다.
static int playGame() {
int score = 0; // 점수 합산
int nowOrder = 0; // 시작 선수
for (int e = 0; e < N; e++) {
int cnt = 1; // 타자는 1로 고정
int out = 0;
while (out < 3) {
int player = order[nowOrder];
int result = ability[e][player];
if (result == 0)
out++;
else {
cnt = cnt << result;
cnt = cnt | 1; // 타자 다시 입력
}
// 점수 확인
if (cnt > 15) {
for (int k = 1 << 4; k < 256; k <<= 1) { // 만루인 상태에서 홈런을 치면 최대 128 비트까지 확인하면 되니깐 k는 256까지
if ((cnt & k) == 0)
continue;
cnt ^= k; // 1 -> 0
score++;
}
}
// 타자 순번 다 돌면 0으로 초기화
if (++nowOrder >= 9) {
nowOrder = 0;
}
}
}
return score;
}비트마스킹을 통해 1은 타석, 2는 1루, 4는 2루, 8은 3루라고 생각한 뒤 시프트 연산을 수행한다. 8비트 이상의 연산이 있으면 홈에 도착한 것으로 판단해서 점수를 합산한다. 순열로 순서를 고려해주는 것 까지는 똑같다.
xor 연산으로 1을 0으로 만들어주어서 초기화 해주는 작업이 존재하고 계속 1에 타석을 두는 것을 확인할 수 있다.
|
128
|
64
|
32
|
16
|
8
|
4
|
2
|
1
|
|
1
|
1
|
1
|
이런 느낌으로 이해하면 될 것 같다!
3109. (골드2) 빵집
import java.io.*;
import java.util.*;
public class Main {
static int R, C;
static char map[][];
static boolean find;
static int cnt;
static void connect(int x, int y) {
if (find)
return;
if (y == C - 1) { // 경로 완성
find = true;
cnt++; // 경로 하나 추가
return;
}
map[x][y] = '*'; // 지나온 길
if (x > 0 && map[x - 1][y + 1] == '.' && !find) // 오른쪽 위
connect(x - 1, y + 1);
if (map[x][y + 1] == '.' && !find) // 오른쪽
connect(x, y + 1);
if (x + 1 < R && map[x + 1][y + 1] == '.' && !find) // 오른쪽 아래
connect(x + 1, y + 1);
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
map = new char[R][C];
for (int i = 0; i < R; i++) {
String row = br.readLine();
for (int j = 0; j < C; j++) {
map[i][j] = row.charAt(j);
}
}
for (int i = 0; i < R; i++) {
find = false;
connect(i, 0);
}
System.out.println(cnt);
}
}
처음에는 0열의 좌표로 부분집합을 만들고 dfs로 탐색을 했다. 당연히 시간초과가 뜰 수 밖에 없었다. (완전탐색이고 R의 크기가 10,000인데 최악의 경우 2^10,000번째까지 부분집합을 만들게 된다. 또 dfs도 500칸인데 방향은 3개이니까 값이 너무 커진다.
한 번 탐색했다가 실패한 길을 다음 탐색에서도 가지 않는다는 점을 이용해서 뒤돌아보지 않는 그리디로 풀어야 하는 문제였다. 또한 오른쪽 위 대각선 (↗)으로 갈 수 있는데 오른쪽으로 가거나 오른쪽 아래 대각선으로 가게 되면 다음 출발 주자의 도달 가능성을 해치게 된다.
탐색에 실패한 곳은 다른 곳에서도 접근하지 못하게 * 표시를 해주는 것이 중요했다.
https://wiselog.tistory.com/140
[백준 3109] 빵집(Java)
https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출
wiselog.tistory.com
'JAVA > BAEKJOON (JAVA)' 카테고리의 다른 글
| 백준 : DAY 1 (Java) (0) | 2024.03.02 |
|---|