📙[Algo] 24.03.23 알고리즘

알고리즘 문제) BOJ 1987. 알파벳

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

문제 요약

• 세로 R, 가로 C칸인 보드
• 각 칸에는 대문자 알파벳 하나씩 적혀 있음
• 1행 1열에 말이 놓여 있음
• 말은 상하좌우 인접한 네칸으로 이동 가능하며, 같은 알파벳을 또 지날 수 없음
• 말이 최대한 몇칸 지날 수 있는지 구하기

시간 제한

• 2초

입력

• R C
  • 1≤R,C≤20
• 보드 정보가 주어짐

출력

• 말이 지날 수 있는 최대 칸 수 출력

접근법

• 백트랙킹으로 풀었다!
• 중복 체크는 set을 사용함
• return후에 set에 원소를 넣었다면 복구시키기 위해 빼줘야 하는데, 그래서 boolean값을 return 하도록 했다.
  • return 값이 false면 set에 못 넣은거니까 제거 안하고
  • true면 넣은 거니까 제거
• 기저 조건에 안 걸리는 테스트케이스도 미리 생각하자
  • 알파벳이 모두 다른 경우 ⇒ set.contains(map[row][col])이것만 조건에 추가하면, 해당 기저에 걸리지 않음
  • 그래서 visitCnt변수를 추가

코드

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

public class Main {
    static int R, C;
    static char[][] map;
    static int[] delR = {-1, 1, 0, 0};
    static int[] delC = {0, 0, -1, 1};
    static boolean[][] visited;
    static Set<Character> set = new LinkedHashSet<>();
    static int ans;

    static boolean dfs(int row, int col, int visitCnt) {

        // 모든 글자가 다른 보드인 경우를 생각해서 기저조건이 하나 더 필요 함
        if (set.contains(map[row][col]) || visitCnt == R * C) {
            if(visitCnt == R * C ) ans = Math.max(ans, set.size() + 1);
            else ans = Math.max(ans, set.size());
            return false;
        }

        visited[row][col] = true;
        set.add(map[row][col]);

        int mrow, mcol;
        boolean ret;
        for (int dir = 0; dir < 4; dir++) {
            mrow = row + delR[dir];
            mcol = col + delC[dir];

            if (mrow < 0 || mcol < 0 || R <= mrow || C <= mcol || visited[mrow][mcol]) continue;

            ret = dfs(mrow, mcol, visitCnt + 1);

            if (ret){
                set.remove(map[mrow][mcol]);
                visited[mrow][mcol] = false;
            }

        }
        return true;
    }

    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());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        map = new char[R][C];
        String input;
        for (int i = 0; i < R; i++) {
            input = br.readLine();
            for (int j = 0; j < C; j++) {
                map[i][j] = input.charAt(j);
            }
        }

        visited = new boolean[R][C];
        dfs(0, 0, 1);

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

 

알고리즘 문제) BOJ 2847. 게임을 만든 동준이

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

문제 요약

• N개의 레벨이 존재
• 점수 = 레벨을 클리어하며 얻은 점수 합
  • 점수 기준으로 온라인 순위를 매김
• 레벨은 난이도 순으로 배치
  • 하지만 낮은 레벨이 더 점수를 많이 받는 경우를 만들어버림
• 따라서 특정 레벨의 점수를 감소 시키고, 각 레벨의 점수가 오름차순이도록 만들려고 함
• 각 레벨의 점수가 주어졌을 때, 몇 번 감소시키면 되는지 구하는 프로그램
  • 점수는 항상 양수여야 하고, 1번 감소 시길 때 1만큼 감소
• 항상 답이 존재하며, 답이 여러가지일 경우 가장 최소한으로 하는 방법을 출력

시간 제한

• 1초

입력

• 레벨의 수 N
  • 1≤N≤100
• N개의 줄에 각 레벨 점수가 주어짐
  • 점수는 2만보다 작은 양수

출력

• 점수를 최소 몇 번 감소시키면 되는지 출력

접근법

음,,,,

어차피 N이 100개만 주어지니까

맨 아래서부터 이전 원소랑 비교하면서 내림차순이 아닐 경우 내림차순 되도록 감소 시키기..?

코드

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[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        int ans = 0, diff;
        for (int i = N - 1; i > 0; i--) {
            if (arr[i] <= arr[i - 1]) {
                diff = arr[i - 1] - arr[i] + 1;
                arr[i - 1] -= diff;
                ans += diff;
            }
        }

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