문제 8. 통증
그리디 문제이다.
그리디 문제의 대명사인 '동전' 문제처럼 가장 큰수부터 빼가면서 문제를 풀이하면 된다.
import java.io.*;
import java.util.*;
class Main {
static int N;
static int[] items = {1, 7, 14};
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
int result = 0;
int i = items.length-1;
while(N > 0) {
if(N == 0) {
break;
}
if(N - items[i] >= 0) {
N -= items[i];
result += 1;
}
else {
i -= 1;
}
}
System.out.println(result);
}
}⚡️ 몫과 나머지를 이용해서 풀이해도 된다.
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
scanner.close();
int ans = 0;
int[] painKiller = {14, 7, 1};
for (int i : painKiller) {
ans += N / i; // 큰 단위로 나누었을 때, 몫
N %= i; // 나머지 -> 다음으로 큰 단위로 나눈다.
}
System.out.println(ans);
}
}
문제 9. 폭탄 구현하기 (2)
완전 탐색 문제이다.
원래 위치와 다음 폭탄의 위치를 함께 확인해야 한다. 본인은 현재 좌표를 기준으로 동서남북에 위치한 폭탄의 위치를 확인하고, 본인 좌표를 확인해서 코드가 다음처럼 길어졌다.
for(int i = 0; i < K; i++) {
st = new StringTokenizer(br.readLine());
int y = Integer.parseInt(st.nextToken()) - 1;
int x = Integer.parseInt(st.nextToken()) - 1;
for(int j = 0; j < 4; j++) {
int n_y = y + dy[j];
int n_x = x + dx[j];
if(n_y < 0 || n_y >= N || n_x < 0 || n_x >= N) {
continue;
}
if(map[n_y][n_x].equals("#")) {
continue;
}
if(map[n_y][n_x].equals("@")) {
result[n_y][n_x] += 2;
}
if(map[n_y][n_x].equals("0")) {
result[n_y][n_x] += 1;
}
}
if(map[y][x].equals("#")) {
continue;
}
if(map[y][x].equals("@")) {
result[y][x] += 2;
}
if(map[y][x].equals("0")) {
result[y][x] += 1;
}
}생각해보니 본인의 현재 위치는 ⚡️0,0⚡️으로 나타낼 수 있다.
따라서 다음과 같이 코드를 수정할 수 있다.
import java.io.*;
import java.util.*;
class Main {
static int N, K;
static String[][] map;
static int[][] result;
static int[] dy = {0,0,1,0,-1};
static int[] dx = {0,1,0,-1,0};
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
map = new String[N][N];
for(int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for(int j = 0; j < N; j++) {
map[i][j] = st.nextToken();
}
}
result = new int[N][N];
for(int i = 0; i < K; i++) {
st = new StringTokenizer(br.readLine());
int y = Integer.parseInt(st.nextToken()) - 1;
int x = Integer.parseInt(st.nextToken()) - 1;
for(int j = 0; j < 5; j++) {
int n_y = y + dy[j];
int n_x = x + dx[j];
if(n_y < 0 || n_y >= N || n_x < 0 || n_x >= N) {
continue;
}
if(map[n_y][n_x].equals("#")) {
continue;
}
if(map[n_y][n_x].equals("@")) {
result[n_y][n_x] += 2;
}
if(map[n_y][n_x].equals("0")) {
result[n_y][n_x] += 1;
}
}
}
int max_value = 0;
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
max_value = Math.max(max_value, result[i][j]);
}
}
System.out.println(max_value);
}
}문제 10. GameJam
이 문제는 계속 안풀려서 답을 봤다.🥲
확인해보니 접근 방식은 맞았는데 풀이 과정 중에 구현 실수를 해서 정답이 되지 않았다.
주석을 달면서 풀이를 이해해보겠다!
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
int[] goormPos = {scanner.nextInt() - 1, scanner.nextInt() - 1};
boolean[][] goormVisited = new boolean[N][N]; // goorm 방문 표시
int[] playerPos = {scanner.nextInt() - 1, scanner.nextInt() - 1};
boolean[][] playerVisited = new boolean[N][N]; // player 방문 표시
String[][] board = new String[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
board[i][j] = scanner.next();
}
}
int goormScore = move(goormPos, goormVisited, 1, board, N);
int playerScore = move(playerPos, playerVisited, 1, board, N);
if (goormScore > playerScore) {
System.out.println("goorm " + goormScore);
} else if (goormScore < playerScore) {
System.out.println("player " + playerScore);
}
scanner.close();
}
public static int set_Pos(int a, int N) {
if (a == -1) return N - 1; // 0보다 작은 곳으로 이동하면 반대편으로 가도록
if (a == N) return 0; // N보다 큰 곳으로 이동하면 반대편으로 가도록
return a;
}
static HashMap<String, int[]> directions = new HashMap<String, int[]>() {
{
put("U", new int[]{-1, 0});
put("D", new int[]{1, 0});
put("L", new int[]{0, -1});
put("R", new int[]{0, 1});
}
};
public static int move(int[] pos, boolean[][] visited, int score, String[][] board, int N) {
int x = pos[0];
int y = pos[1];
visited[x][y] = true;
boolean flag = true;
while (flag) {
String command = board[x][y];
// distance는 direction 문자열 앞까지를 말한다.
int distance = Integer.parseInt(command.substring(0, command.length() - 1));
// 가장 마지막에 위치한 것은 direction
String direction = command.substring(command.length() - 1);
for (int i = 0; i < distance; i++) {
x += directions.get(direction)[0];
y += directions.get(direction)[1];
x = set_Pos(x, N);
y = set_Pos(y, N);
if (!visited[x][y]) {
visited[x][y] = true;
score += 1;
} else {
flag = false; // 이미 방문했다면 게임이 종료된다.
break;
}
}
}
return score;
}
}나의 시도는 게임을 진행하다가 게임 종료 조건을 만나면 바로 게임을 현재 게임 참여자의 flag를 바꿔서 게임을 종료시키는 것이었는데, goorm과 player의 score 변수를 두개로 관리하다보니 풀이가 복잡해졌다. 이 풀이는 score를 return 해서 goorm과 player 중 승자를 비교하는데 이 풀이가 더 적합하다고 생각한다.
벌써 2주차가 지났다.
하루하루 블록이 쌓아가는 것 보면 뿌듯하다.👊 다음주는 탐색과 DP 문제를 푸는데 평소에 연습이 필요하다고 생각했던 단원이라 더욱 기대된다. 그럼 마지막까지 화이팅~
반응형
