문제 1 / 회전 방어
목표 : N초 동안 차감되는 점수의 합이 최솟값을 구하기
해결방법 : 매 라운드 마다 현재 바라보는 방향에 따라 가해지는 피해량이 달라지므로 공격 방향을 선택하여 누적 피해를 최소화 하도록 다이나믹 프로그래밍을 이용해 해결했다.
enemies의 값은 행이 상우하좌고 열이 공격받는 시간이었다. 그래서 board라는 이차원 배열로 행이 공격받는 시간으로 열이 상우하좌로 변경해줬다. 그 후 바라보는 상우하좌 바라보는 방향에 따라 공격력의 가중치가 달라지므로 mul에 맞춰서 설정해줬다.
각 라운드별로 가만히, 우회전, 좌회전 3가지 경우로 해당 방향에 맞는 가중치를 곱해 누적해준 후 dp 테이블에 현재까지 누적피해와 이번 라운드 피해를 더한 값과 기존의 값 중 최솟 값을 업데이트해줬다.
모든 라운드가 종료된 후, 각 방향에 대해 최솟값이 최종 최소 누적 피해량으로 리턴해줬다.
import java.util.*;
class Solution {
static int answer;
static int[][] board;
static int[][] dp;
public int solution(int N, int[][] enemies) {
answer = Integer.MAX_VALUE;
board = new int[N][4];
dp = new int[N+1][4];
// 상하좌우를 로우 -> 컬럼으로 변경
for(int i=0; i<N; i++) {
board[i][0] = enemies[0][i];
board[i][1] = enemies[1][i];
board[i][2] = enemies[2][i];
board[i][3] = enemies[3][i];
}
// 바라보는 방향 기준 공격력
int[][] mul = {
{1, 2, 3, 2},
{2, 1, 2, 3},
{3, 2, 1, 2},
{2, 3, 2, 1}
};
for(int i=0; i<=N; i++) {
Arrays.fill(dp[i], Integer.MAX_VALUE);
}
dp[0][0] = 0;
for(int i=0; i<N; i++) {
for(int d=0; d<4; d++) {
if(dp[i][d]==Integer.MAX_VALUE) continue;
// 가만히
int nextDir = d;
int damage = 0;
for(int j=0; j<4; j++) {
damage += board[i][j]*mul[nextDir][j];
}
dp[i+1][nextDir] = Math.min(dp[i+1][nextDir], dp[i][d]+damage);
// 우회전
nextDir = (d+1)%4;
damage = 0;
for(int j=0; j<4; j++) {
damage += board[i][j]*mul[nextDir][j];
}
dp[i+1][nextDir] = Math.min(dp[i+1][nextDir], dp[i][d]+damage);
// 좌회전
nextDir = (d+3)%4;
damage = 0;
for(int j=0; j<4; j++) {
damage += board[i][j]*mul[nextDir][j];
}
dp[i+1][nextDir] = Math.min(dp[i+1][nextDir], dp[i][d]+damage);
}
}
for(int d=0; d<4; d++) {
answer = Math.min(answer, dp[N][d]);
}
return answer;
}
}문제 2 / 기사 배치하기
목표 : 각 기사들이 겹치지 않고 보드에 주어진 점수로 최대 1번만 이동해서 얻을 수 있는 점수의 합의 최댓값 구하기
해결방법 : 백트레킹(DFS)를 이용해 풀었다.
각 기사의 위치를 구해주고 각 기사마다 이동 가능한 부분을 모두 탐색하며 겹치지 않는 배치를 찾고 점수 합을 계산했다.
- 기사의 위치를 저장한다.
- 각 기사마다 이동 가능한 부분들을 구한다.
- 모든 이동 경우를 고려해 이동 가능한 칸의 점수를 함께 저장
- visited 배열을 사용해 기사가 해당 칸을 사용하지 않을 때와 사용할 때를 표시해줘서 겹치지 않게 해줌
- 백트래킹(DFS)를 이용하여 각 기사의 이동 가능한 부분들을 선택하며 최대 점수 합을 구한다.
import java.util.*;
class Solution {
static int N, K, answer;
static int[][] board;
static boolean[][] visited;
// 기사 이동 가능한 경우(8가지 이동방법과 가만히 있는 경우)
static int[][] moves = {
{0, 0}, {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2},
{1, 2}, {2, 1}, {2, -1}, {1, -2}
};
// 기사의 초기 위치
static class Point {
int y, x;
public Point(int y, int x) {
this.y = y;
this.x = x;
}
}
// 이동 후 위치와 점수를 저장하는 클래스
static class Move {
int y, x, score;
public Move(int y, int x, int score) {
this.y = y;
this.x = x;
this.score = score;
}
}
// 기사 위치 담을 리스트
static ArrayList<Point> knights;
// 각 기사별로 이동 가능한 부분들 저장할 리스트 배열
static ArrayList<Move>[] knightsMoves;
public int solution(int N, int K, int[][] board) {
this.N = N;
this.K = K;
this.board = board;
visited = new boolean[N][N];
answer = Integer.MIN_VALUE;
knights = new ArrayList<>();
for(int y=0; y<board.length; y++) {
for(int x=0; x<board[y].length; x++) {
if(board[y][x]==0) {
knights.add(new Point(y, x));
}
}
}
knightsMoves = new ArrayList[knights.size()];
for(int i=0; i<knights.size(); i++) {
knightsMoves[i] = new ArrayList<>();
int y = knights.get(i).y;
int x = knights.get(i).x;
for(int[] move : moves) {
int ny = y + move[0];
int nx = x + move[1];
if(ny<0 || nx<0 || ny>=N || nx>=N) continue;
knightsMoves[i].add(new Move(ny, nx, board[ny][nx]));
}
}
dfs(0, 0);
return answer;
}
static void dfs(int idx, int sum) {
if(idx==knights.size()) {
answer = Math.max(answer, sum);
return;
}
for(Move move : knightsMoves[idx]) {
if(!visited[move.y][move.x]) {
visited[move.y][move.x] = true;
dfs(idx+1, sum+move.score);
visited[move.y][move.x] = false;
}
}
}
}문제 3 / 소수 판별
목표 : A이상 B이하 숫자 중 소수를 판별
해결방법 : 최소 약수는 루트num 이하에 있으므로 반복 범의를 루트num으로 줄여 시간 복잡도를 낮춰서 풀었습니다.
크게 2 나 5로 나뉘어지면 소수가 아니기 때문에 예외처리를 하고 그 후엔 소수 판별을 해준다.
1자리 숫자 중에 소수는 2, 3, 5, 7이 있기 때문에 i, i+2중 나뉘어 진다면 소수가 아니게 되기 때문에 소수 판별을 저렇게 해주었다.
class Solution {
public int solution(int A, int B) {
int answer = 0;
if(A==B) return 0;
for(int i=A; i<=B; i++) {
if(i%2==0 || i%5==0) {
continue;
}
if(isPrimeNum(i)) {
answer++;
}
}
return answer;
}
static boolean isPrimeNum(int num) {
for(int i=2; i*i<=num; i++) {
if(num%i==0 || num%(i+2)==0) {
return false;
}
}
return true;
}
}
개발자가 되고 싶은 취준생