알고리즘 문제풀이 3-4

문제 1 / 회전방어

-목표 : N초 동안 최적의 행동을 함으로써 만들 수 있는, 차감되는 점수의 합의 최솟값을 반환하는 프로그램 구

 

문제 풀이

 

최종 코드

import java.util.Arrays;
class Solution {
    public int solution(int N, int[][] enemies) {
        int answer = 0;
        int[][] dp = new int[N][4];

        for (int d = 0; d < 4; d++) {
            dp[0][d] = calcDamage(enemies, d, 0);
        }

        for (int t = 1; t < N; t++) {
            for (int d = 0; d < 4; d++) {
                dp[t][d] = Integer.MAX_VALUE;

                dp[t][d] = Math.min(dp[t][d], dp[t - 1][d] + calcDamage(enemies, d, t));

                dp[t][d] = Math.min(dp[t][d], dp[t - 1][(d + 3) % 4] + calcDamage(enemies, d, t));

                dp[t][d] = Math.min(dp[t][d], dp[t - 1][(d + 1) % 4] + calcDamage(enemies, d, t));
            }
        }
        return Arrays.stream(dp[N - 1]).min().getAsInt();
    }


    private int calcDamage(int[][] enemies, int d, int t) {
        int damage = 0;
        for (int i = 0; i < 4; i++) {
            int multiplier = 1;
            if ((d + 2) % 4 == i) multiplier = 3;
            else if ((d + 1) % 4 == i || (d + 3) % 4 == i) multiplier = 2;

            damage += enemies[i][t] * multiplier;
        }
        return damage;
    }
}

---

문제 2 / 기사 배치하기

-목표 : 기사들이 최적의 경로를 찾아 이동하면서 최대한의 점수를 구하는 프로그램 구현

 

문제 풀이

반복문을 이용하여 최댓값과 최소값을 구한 뒤 차를 반환하였다.

 

최종 코드

 

---

문제 3 / 소수 판별

-목표 : 자연수 형태의 A 와 B 가 주어졌을 때, A이상 B이하의 모든 자연수 중에서 소수의 개수를 반환하는 프로그램 구현

 

문제 풀이

 

최종 코드

import java.util.*;
class Solution {
    public int solution(int A, int B) {
        int answer = 0;
        boolean[] isPrime = new boolean[B - A + 1];
        Arrays.fill(isPrime, true);

        for(long i = 2; i * i<= B; i++){
            long start = Math.max(i * i, (A + i - 1) / i * i);
            for(long j = start; j <= B; j+= i){
                isPrime[(int)(j - A)] = false;
            }
        }
        if(A == 1) isPrime[0] = false;
        for(boolean prime : isPrime){
            if(prime) answer++;
        }
        return answer;
    }
}

---