📙[Algo] 24.03.02 알고리즘

알고리즘 문제) BOJ 18111. 마인크래프트

• 링크 : https://www.acmicpc.net/problem/18111

문제 요약

• 세로 N, 가로 M 크기의 집터가 있을 때, 땅의 높이를 모두 일정하게 바꾸려고 함
• 이를 위해 다음 두 종류의 작업을 할 수 있음
  1. 좌표 (i,j)의 가장 위에 있는 블록을 제거하여 인벤토리에 넣는다.
  2. 인벤토리에서 블록하나를 꺼내 좌표 (i,j)의 가장 위에 있는 블록 위에 놓는다.
• 1번 작업은 2초, 2번 작업은 1초가 걸림
• 땅 고르기 작업에 걸리는 최소 시간과 그 때 땅의 높이를 출력
• 인벤토리에는 B개의 블록이 들어 있음
• 땅의 높이는 음수가 될 수 없음

시간 제한

• 1초

입력

• N M B
  • 1≤M,N≤500
  • 0≤B≤6.4*1000만
• N개의 줄에 각각 M개의 정수로 땅의 높이가 주어짐
  • 땅의 높이는 256보다 작거나 같은 자연수 또는 0

출력

• 땅을 고르는데 걸리는 최소 시간과 땅의 높이 출력
  • 여러 개라면 그 중 땅의 높이가 가장 높은 것 출력

접근법

1. 완전 탐색으로 접근하기
   • 높이는 최대 256까지 가능하다.
   • 256부터 아래로 하나씩 내려가면서 해당 높이로 고르게 할 수 있는지 체크하기
   • 시간을 최소 시간으로 갱신하면서, 높이도 함께 기록.
   • 만약 시간이 같다면 가장 높은 높이로 갱신.

코드

• 자칫하다 실수할 수 있는 문제!
  • 다른 칸에서 제거한 블록을 가져다 쓸 수 있음에 주의

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());   // 세로 길이
        int M = Integer.parseInt(st.nextToken());   // 가로 길이
        int B = Integer.parseInt(st.nextToken());   // 인벤토리 블럭 개수

        // 맵 상태 입력 받기
        int[][] map = new int[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int minCost = Integer.MAX_VALUE;    // 최소 비용
        int height = 0; // 최소 비용일 때 땅의 높이
        int cost, inven, needBlock;    // 비용, 인벤토리에 저장된 블럭, 필요로 하는 블럭
        for (int h = 256; h >= 0; h--) {
            cost = 0;
            inven = B;
            needBlock = 0;

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (map[i][j] < h) {
                        // 현재칸의 땅의 높이가 목표로 하는 땅의 높이보다 작을 때

                        // 일단 필요한 블럭 개수를 기록한다
                        // 여기서 미리 이벤토리 블럭개수랑 비교해서 가능, 불가능 판단하면 X
                            // 다른 칸에서 블럭을 제거한다음 가져와서 쓸 수 있을 수도 있으니까.
                        needBlock += (h - map[i][j]);

                    } else if (map[i][j] > h) {
                        // 현재칸의 땅의 높이가 목표로 하는 땅의 높이보다 클 때

                        inven += (map[i][j] - h);   // 블록을 제거한 만큼 인벤토리에 넣기
                        cost += (map[i][j] - h) * 2;    // 비용 계산

                    }
                }
            }

            if (needBlock <= inven) {
                cost += needBlock;
                if (minCost > cost) {
                    minCost = cost;
                    height = h;
                } else if (minCost == cost) {
                    if(height < h) height = h;
                }
            }
        }

        bw.write(String.valueOf(minCost + " " + height));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 1676. 팩토리얼 0의 개수

• 링크 : https://www.acmicpc.net/problem/1676

문제 요약

• N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수 출력

시간 제한

• 2초

입력

• N
  • 0≤N≤500

출력

• 0의 개수 출력

접근법

• n!에 곱해져 있는 2의 개수와 5의 개수를 찾고, 그중 최솟값만큼 0의 개수가 된다.
  • 2*5의 쌍의 개수 찾는 것
• 2의 개수 찾기
  • 1~N까지 돌면서 2로 나누어 떨어지는 거 카운트
• 5의 개수 찾기
  • 1~N까지 돌면서 5로 나누어 떨어지는 거 카운트

코드

import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());

        int tmp;
        int twoCnt = 0, fiveCnt = 0;
        for (int i = 1; i <= N; i++) {
            tmp = i;
            while (tmp % 2 == 0) {
                twoCnt++;
                tmp /= 2;
            }

            tmp = i;
            while (tmp % 5 == 0) {
                fiveCnt++;
                tmp /= 5;
            }
        }

        bw.write(String.valueOf(Math.min(twoCnt, fiveCnt)));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 18110. solved.ac

• 링크 : https://www.acmicpc.net/problem/18110

문제 요약

• 난이도 선정
  • 아무 의견이 없다면 0
  • 하나 이상 있다면, 모든 사람 난이도 의견의 30% 절사 평균
    • 절사 평균 : 가장 큰 값들과 가장 작은 값들을 제외하고 평균 내는 것
      • 30% 절사 평균 : 위에서 15%, 아래에서 15%를 각각 제외하고 평균 계산
        • 제외되는 사람의 수는 위, 아래에서 각각 반올림
• 난이도 의견 목록이 주어질 때, 난이도 계산하는 프로그램 작성

시간 제한

• 1초

입력

• 난이도 의견 개수 n
  • 0≤n≤3*100000
• n개의 줄에 사용자들이 제출한 난이도 의견이 주어

출력

• solved.ac가 계산한 문제의 난이도를 출력

접근법

• 반올림 주의! ⇒ Math.round
• double변환 해야

코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());

        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(arr);

        int startIdx = (int)Math.round(N * 0.15);
        int endIdx = N - (int) Math.round(N * 0.15);

        int sum = 0;
        for (int i = startIdx; i < endIdx; i++) {
            sum += arr[i];
        }

        bw.write(String.valueOf(Math.round((double)sum / (endIdx - startIdx))));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 1259. 팰린드롬수

• 링크 : https://www.acmicpc.net/problem/1259

문제 요약

• 뒤에서부터 읽어도 똑같다면 팰린드롬
• 12421은 팰린드롬수
• 그러나 10은 팰린드롬수가 아니다 → 앞에 무의미한 0이 올 수 있다면 010이 되어 가능할 수 있지만, 이번에는 불가능하다고 생각하기

시간 제한

• 1초

입력

• 각 줄마다 1이상 99999이하의 정수가 주어짐
• 마지막 줄에는 0이 주어짐

출력

• 주어진 수가 팰린드롬수면 ‘yes’, 아니면 ‘no’

접근법

• 최대 5자리 정수가 주어지므로 그냥 앞뒤 같은지 비교하면 될 듯
  • ex) 4 자리 수
    • for i=0~1
      • arr[i] == arr[len-i-1]

코드

import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        String num; boolean isSame;
        while (true) {
            num = br.readLine();

            if(num.equals("0")) break;

            isSame = true;
            for (int i = 0; i < num.length() / 2; i++) {
                if (num.charAt(i) != num.charAt(num.length() - i - 1)) {
                    isSame = false;
                    break;
                }
            }

            if (!isSame) sb.append("no\\n");
            else sb.append("yes\\n");
        }

        bw.write(String.valueOf(sb));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 15829. Hashing

• 링크 : https://www.acmicpc.net/problem/15829

문제 요약

• 아래식을 통해 문자열의 해시값 계산하기
  

  

  • r : 31
  • M : 1234567891
• 문자는 a→1, b→2, … , z → 26으로 고유한 번호 부여

시간 제한

• 1초

입력

• 문자열 길이 L
  • 1≤L≤50
• 소문자로만 이루어진 문자열

출력

• 해시함수와 입력으로 주어진 문자열을 사용해 계산한 해시 값 출력

접근법

• 데이터 범위 벗어날 수 있는 부분마다 모듈러 연산 적용해야

코드

import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int L = Integer.parseInt(br.readLine());
        final int MOD = 1234567891;
        String str = br.readLine();

        long sum = 0;
        long mul = 1;
        for (int i = 0; i < str.length(); i++) {
            sum = (sum + (str.charAt(i) - 'a' + 1) * mul % MOD) % MOD;
            mul = (mul * 31) % MOD;
        }

        bw.write(String.valueOf(sum));
        bw.flush();
        bw.close();
        br.close();
    }
}