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)


문제 링크 : https://www.acmicpc.net/problem/7576


제 생각하는 가장 기본적인 BFS 문제입니다.


만약 누군가 BFS 개념을 이제 막 배워서 문제를 추천해달라고 한다면 이 문제를 추천할 겁니다.



<접근>


하루에 상, 하, 좌, 우 한 칸씩 이동하니 BFS가 바로 떠오릅니다.


저는 좌표 관련된 BFS 문제에서는 좌표에 대한 Class를 만들어서 사용합니다.


아래 그림처럼 배열의 숫자를 하나씩 증가시키는 방법도 있지만





저는 클래스에 변수를 하나 더 추가하여 카운트 하는 방법로 풀었습니다.


일반적으로 BFS 문제에서는 visited 2차원 배열을 사용하여 중복 방문을 방지하지만 이 문제에서는 1 이 그 역할을 하고 있습니다.






<순서>


1. 2중 for문으로 box 배열을 돌면서 익은 토마토를 Queue 자료구조에 넣기


2. bfs를 돌면서 토마토 모두 익게 하기


3. 다시 2중 for문 돌면서 안 익은 토마토가 있다면 -1 출력, 없으면 날짜 출력


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)


문제 링크 : https://www.acmicpc.net/problem/1436



666을 포함하는 N 번째 숫자를 출력하는 문제입니다.


한가지 주의할 점은 666이 연속으로 들어가야 하기 때문에 6606, 6066 같은 숫자는 제외된다는 점입니다.


1.  while 문을 통해 숫자를 하나씩 증가시킴

2.  "666"을 포함하는지 비교

3.  만약 포함한다면 N을 1씩 감소시킨 후 N이 0이 되면 break


문제 링크 : https://www.acmicpc.net/problem/1181



N 개의 단어를 받아서


1. 길이가 짧은 것부터

2. 길이가 같으면 사전 순으로


정렬하여 출력하는 문제입니다.


하지만 문제를 자세히 읽어보면 중복된 단어의 경우 한번만 출력한다는 조건이 하나 더 있습니다.


그래서 입력받은 문자를 Set 자료구조에 담아서 중복을 제거한 뒤에 ArrayList로 옮겨서 정렬해주었습니다.


+ Recent posts