Problem


문제에서 시키는 대로 주사위를 굴리는 문제입니다.



Solution

특별한 알고리즘은 없고 문제에서 제시한 대로 구현만 해주면 됩니다.


언뜻 보면 굉장히 복잡한 것 같지만 주사위가 동, 서, 남, 북으로 이동하는 부분만 하드코딩 해주면 간단하게 풀립니다.


저는 Dice라는 클래스를 만들어서 주사위 6면의 값을 저장했습니다.


방향은 동쪽은 1, 서쪽은 2, 북쪽은 3, 남쪽은 4기 때문에 dxdy 배열을 만들때 저 순서대로 만든 후에 1씩 빼주면 됩니다.


함정에 빠질만한 부분이라면 지도의 값이 0이 아닐때 주사위 바닥에 복사를 하는데, 복사 하고 나면 지도값은 0이 되는겁니다.


순서는 문제에 나와있는 대로


  1. 입력받은 방향만큼 for
  2. 움직인 이후의 값이 지도를 벗어나는지 확인
  3. 주사위 이동
  4. 숫자 복사
  5. 맨 윗면 출력


이 순서대로 k번만큼 진행하면 됩니다.


주사위를 이동시킬 때 자바는 temp 값을 사용했지만 파이썬은


x, y = y, x


이렇게 두개의 값을 바꿀수 있다는 특성을 이용하여 구현할 수 있습니다.



Java Code

import java.util.*;
import java.io.*;

class Main {
    static class Dice {
        int top, bottom, west, east, south, north;

        public Dice() {
            this.top = 0;
            this.bottom = 0;
            this.west = 0;
            this.east = 0;
            this.south = 0;
            this.north = 0;
        }

        public void moveEast() {
            int temp = top;
            top = west;
            west = bottom;
            bottom = east;
            east = temp;
        }

        public void moveWest() {
            int temp = top;
            top = east;
            east = bottom;
            bottom = west;
            west = temp;
        }

        public void moveSouth() {
            int temp = top;
            top = north;
            north = bottom;
            bottom = south;
            south = temp;
        }

        public void moveNorth() {
            int temp = top;
            top = south;
            south = bottom;
            bottom = north;
            north = temp;
        }

        public void printTopNumber() {
            System.out.println(top);
        }
    }

    static int n, m, x, y, k;
    static int[][] map;
    static int[] dir;
    static int[] dx = {0, 0, -1, 1};    // 동서북남
    static int[] dy = {1, -1, 0, 0};

    static int stoi(String s) {
        return Integer.parseInt(s);
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = stoi(st.nextToken());
        m = stoi(st.nextToken());
        x = stoi(st.nextToken());
        y = stoi(st.nextToken());
        k = stoi(st.nextToken());
        map = new int[n][m];
        dir = new int[k];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j] = stoi(st.nextToken());
            }
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < k; i++) {
            dir[i] = stoi(st.nextToken());
        }

        solution();
    }

    static void solution() {
        Dice dice = new Dice();
        int nx, ny;

        for (int i = 0; i < k; i++) {
            int direction = dir[i] - 1;
            nx = x + dx[direction];
            ny = y + dy[direction];

            if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                // 동쪽은 0, 서쪽은 1, 북쪽은 2, 남쪽은 3
                if (direction == 0) dice.moveEast();
                else if (direction == 1) dice.moveWest();
                else if (direction == 2) dice.moveNorth();
                else if (direction == 3) dice.moveSouth();

                // 숫자 복사
                if (map[nx][ny] == 0)
                    map[nx][ny] = dice.bottom;
                else {
                    dice.bottom = map[nx][ny];
                    map[nx][ny] = 0;
                }

                // 맨 윗면 출력
                dice.printTopNumber();

                x = nx;
                y = ny;
            }
        }
    }
}



Python Code

# -*- coding: utf-8 -*-
 
import sys
 
N = M = K = 0
arr = []
## 동 서 북 남
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
 
## x, y 좌표와 주사위 상단/하단/동/서/남/북 면에 있는 숫자
class Dice:
    def __init__(self, x, y, top, bottom, e, w, n, s):
        self.x = x
        self.y = y
        self.top = top
        self.bottom = bottom
        self.e = e
        self.w = w
        self.n = n
        self.s = s
 
def move(dice, d):
    nx = dice.x + dx[d]
    ny = dice.y + dy[d]
 
    ## 지도 밖으로 안나가야 됨
    if 0 <= nx and nx < N and 0 <= ny and ny < M:
        dice.x = nx
        dice.y = ny
 
        ## 동 서 북 남
        if d == 0:
            dice.top, dice.bottom, dice.w, dice.e = dice.w, dice.e, dice.bottom, dice.top
        elif d == 1:
            dice.top, dice.bottom, dice.w, dice.e = dice.e, dice.w, dice.top, dice.bottom
            pass
        elif d == 2:
            dice.top, dice.bottom, dice.n, dice.s = dice.s, dice.n, dice.top, dice.bottom
        elif d == 3:
            dice.top, dice.bottom, dice.n, dice.s = dice.n, dice.s, dice.bottom, dice.top
 
        ## 이동한 칸이 0이면 주사위 바닥면 복사
        ## 이동한 칸이 0이 아니면 주사위 바닥면에 숫자 복사하고 칸은 0
        if arr[dice.x][dice.y] == 0:
            arr[dice.x][dice.y] = dice.bottom
        else:
            dice.bottom = arr[dice.x][dice.y]
            arr[dice.x][dice.y] = 0
    else:
        return False
 
    return True
 
def solve(x, y, directions):
    dice = Dice(x, y, 0, 0, 0, 0, 0, 0)
 
    for direction in directions:
        if move(dice, direction-1) == True:
            print(dice.top)
 
if __name__ == '__main__':
    N, M, x, y, K = map(int, sys.stdin.readline().split())
 
    for i in range(N):
        arr.append(list(map(int, sys.stdin.readline().split())))
 
    directions = list(map(int, sys.stdin.readline().split()))
 
    solve(x, y, directions)


Problem


각 시험장의 응시생을 모두 감독하기 위해 필요한 감독관의 최소값을 구하는 문제입니다.



Solution

Greedy 문제입니다.


각 방마다 총 감독관은 꼭 한명씩 있어야 하기 때문에 빼줍니다.


만약 총감독관 - 감시 학생 수 > 0 이라면 부감독관이 필요하다는 뜻입니다.


부감독관은 남은 학생 수 / 부감독관의 감시 학생 수 만큼 필요합니다.


만약 딱 나누어 떨어지지 않는 경우 부감독관이 한명 더 필요합니다.


그래서 남은 학생 수 % 부감독관의 감시 학생 수 != 0 라면 부감독관을 한명 더 추가해주어야 합니다.


나머지가 0 으로 딱 나누어 떨어진다면 추가할 필요가 없습니다.


간단한 문제이지만 많이 틀리는 이유는 자료형 때문이라고 생각합니다.


100만개의 시험장에 100만명의 학생들이 들어가있는데 총감독관과 부감독관이 감시하는 학생 수가 1명밖에 안된다면

총 감독관은 100만 * 100만 만큼 필요하게 됩니다.


int 형으로는 커버할 수 없으므로 total 변수를 long으로 선언해줍니다.


파이썬은 해당되지 않습니다. 그냥 계산해주시면 됩니다.



Java Code

import java.util.*;
import java.io.*;
 
class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int n = Integer.parseInt(br.readLine());
        int[] a = new int[n];
 
        st = new StringTokenizer(br.readLine());
        for (int i=0; i<n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }
 
        st = new StringTokenizer(br.readLine());
        int b = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
 
        long total = n;
        for (int i=0; i<n; i++) {
            // 총감독관은 무조건 한명씩 필요
            a[i] -= b;
 
            // 부감독관으로 나머지 채우기
            if (a[i] > 0) {
                total += a[i]/c;
 
                if(a[i] % c != 0) {
                    total++;
                }
            }
        }
 
        System.out.println(total);
    }
}



Python Code

# -*- coding: utf-8 -*-
 
import sys
 
N = B = C = 0
 
def solve(A):
    count = 0
 
    for i in range(N):
        ## 각 반에서 총 감독관은 한명씩 필요
        if A[i] > 0:
            A[i] -= B
            count += 1
        
        ## 나머지 부감독관으로 채우기
        if A[i] > 0:
            count += int(A[i]/C)
 
            if A[i] % C != 0:
                count += 1
 
    return count
 
if __name__ == '__main__':
    N = int(sys.stdin.readline())
    A = list(map(int, sys.stdin.readline().split()))
    B, C = map(int, sys.stdin.readline().split())
 
    result = solve(A)
    print(result)


Problem


앞으로 남은 근무일과 상담일정이 주어졌을 때 상담으로 얻는 최대 수익을 구하는 문제입니다.



Solution

DP 문제입니다.


for 문을 뒤에서부터 시작하여 dp 값을 차곡차곡 쌓아서 dp[1] 을 출력해주면 됩니다.


example


1일에는 3일동안 상담을 할 수 있으므로 1, 2, 3 일을 소모하게 됩니다.


그럼 최대한 많은 금액을 받기 위해서는


1일 금액 + 4일부터 받을 수 있는 최대 금액


이것이 1일에 상담을 할 경우 얻을 수 있는 최대 금액입니다.


x일부터 받을 수 있는 최대 금액을 저장하기 위해 dp 배열을 사용합니다.


P[1] + dp[4] 라는 첫번째 식을 얻었습니다.


그런데 1일에 상담을 하는 경우보다 2일에 상담을 하는 경우가 최고 금액일 수 있습니다.


예를 들어 P[1] + dp[4] 의 금액이 50인데 dp[2] 가 100 일 가능성이 있습니다.


그러므로 두 개의 값 중 더 큰 값이 1일부터 받을 수 있는 최대 금액입니다.


dp[1] = MAX(P[1] + dp[4], dp[2])


일반 수식으로 변환하면


dp[i] = MAX(P[i] + dp[i+T[i]], dp[i+1])


만약 상담일이 퇴사일을 초과하면 자동으로 dp[i+1] 의 값이 받을수 있는 최대금액이 됩니다.


마지막 날에도 1일의 상담을 할 수 있습니다. i + T[i] <= N + 1 로 수식을 세워야 합니다.


대신 배열을 선언할 때 1 의 여유공간을 추가로 더 선언합니다.



Java Code

import java.util.*;
import java.io.*;
import java.lang.*;

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        int[] T = new int[N + 2];
        int[] P = new int[N + 2];
        int[] dp = new int[N + 2];

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            T[i] = Integer.parseInt(st.nextToken());
            P[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = N; i > 0; i--) {
            int day = i + T[i];     // i번째 날의 상담기간

            if (day <= N + 1)
                dp[i] = Math.max(P[i] + dp[day], dp[i + 1]);
            else    // 상담일 초과
                dp[i] = dp[i + 1];
        }

        System.out.println(dp[1]);
    }
}



Python Code

# -*- coding: utf-8 -*-
 
import sys
 
def solve(n, t, p):
    dp = [0 for i in range(n)]
    
    ## 초기값
    ## 1일간만 상담해야 들어갈 수 있음
    if t[n-1] == 1:
        dp[n-1] = p[n-1]
 
    ## 뒤에서부터 계산함
    for i in range(n-2, -1, -1):
        day = i + t[i]
 
        ## 상담가능일이 n이랑 똑같으면 이후엔 상담불가능
        if day == n:
            dp[i] = max([p[i], dp[i+1]])
        ## 상담 가능일이 n보다 작으면 이후에 상담가능
        elif day < n:
            dp[i] = max([p[i] + dp[day], dp[i+1]])
        elif day > n:
            dp[i] = dp[i+1]
 
    print(dp[0])
 
if __name__ == '__main__':
    n = int(sys.stdin.readline())
    t = []
    p = []
 
    for i in range(n):
        ti, pi = map(int, sys.stdin.readline().split())
        t.append(ti)
        p.append(pi)
 
    solve(n, t, p)


+ Recent posts