📙[Algo] 24.05.08 알고리즘

알고리즘 문제) BOJ 1562. 계단 수

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

문제 요약

• 계단 수 : 인접한 모든 자리의 차이가 1
• N이 주어질 때 길이가 N이면서 0부터 9까지 숫자가 모두 등장하는 계단수가 총 몇 개인지 구하기

시간 제한

• 2초

입력

• 첫째줄에 N이 주어진다.
  • 1 ≤ N <≤ 100, 자연수

출력

• 정답을 1000000000로 나눈 나머지 출력

접근법

• 비트마스크 공부 다시하고 풀었다.
• N이 100까지 가능하고 각각 들어갈 수 있는 숫자가 0~9이기때문에 최악의 경우 나올 수 있는 경우의 수가 9^100으로 그냥 백트랙킹으로 풀면 안된다.
• 나는 탑다운DP 알고리즘으로 풀었다.
• recur(int cur, int prv, int numCnt)
  • cur → 현재 가리키는 자릿수(앞에서부터 하나씩 쌓아감)
  • prv → 이전에 가리켰던 수
  • numCnt → 선택한 숫자 갯수
• 비트마스크는 언제 사용하는가?
  • 이 문제를 풀다보면 언제 어떤 숫자를 선택했는지에 따라 경우의 수가 나뉘어 진다.
  • 그리고 총 0~9까지 10개의 숫자를 모두 선택해야한다.
  • 위 2가지 조건을 고려할 때, 각 숫자를 선택했는지 안 했는지를 10자리 2진수로 풀어서 선택 여부를 체크할 수 있다.
    • 지금까지 0을 선택했다면 0000000001
    • 지금까지 9 2 0을 선택했다면 1000000101
    • 이런식으로 체크해가면서 진행할 것이다
  • 그리고 매개변수 numCnt에 현재까지 선택한 비트값을 보내준다.
    • 이때 이전까지 선택했던 숫자를 저장한 numCnt와 현재 선택한 숫자를 저장한 값을 OR연산(|)해서 넘겨줘야 한다. ⇒ 누적해서 기록
• 사실, 여기서 복병은 나머지 연산을 하고 넘겨주는 부분이다.
  • 원래는 복합대입연산자 += 사용해서 ret += recur(cur + 1, i, numCnt | (1 << i))% MOD 이런식으로 했는데, 그러면 계산 과정에서 모듈러 연산이 제대로 처리 되지 않는 것 같았다. 그래서 그냥 안전한게 결과 값 나오는 부분마다 모듈러 연산을 적용했다. ⇒ 보통 이런 문제는 중간에 나누기가 있지 않는 이상 계산 중간과정마다 모듈러 연산 붙이는게 안전한 듯…

코드

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

public class Main {
    static int N;
    static int[] selected = new int[110];
    static int[][][] dp = new int[110][10][1 << 10];
    static final int MOD = 1_000_000_000;


    static int recur(int cur, int prv, int numCnt) {
        if (cur == N) {
            if (numCnt == 1023) {
                return 1;
            } else {
                return 0;
            }
        }

        if (dp[cur][prv][numCnt] != -1) return dp[cur][prv][numCnt];

        int ret = 0;
        for (int i = 0; i < 10; i++) {

            // 이전 숫자와의 차이가 1이 아니라면 pass
            if (Math.abs(prv - i) != 1) continue;

            selected[cur] = i;

            ret = (ret + recur(cur + 1, i, numCnt | (1 << i)) % MOD) % MOD;

        }

        dp[cur][prv][numCnt] = ret;
        return ret;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        for (int[][] d1 : dp) {
            for (int[] d2 : d1) {
                Arrays.fill(d2, -1);
            }
        }

        int ans = 0;
        for (int i = 1; i <= 9; i++) {
            ans = (ans + recur(1, i, 1 << i) % MOD) % MOD;
        }

        System.out.println(ans);
        br.close();
    }
}

 

알고리즘 문제) BOJ 3151. 합이 0

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

문제 요약

• 학생 3명을 골라 코딩 실력의 합이 0이 되는 경우를 출력

시간 제한

• 4초

입력

• 첫째줄 : 학생수 N
• 둘째줄 : 학생들의 코딩실력이 주어짐다.
  • 실력은 -10000~10000

출력

• 선택할 수 있는 팀의 모든 경우의 수 출력

접근법

• 투포인터로 접근했으나, 중복 제거하는 문제로 골치아팠던 문제
• 굳이 두 수를 합한 배열을 따로 만들 필요 X ⇒ 이거는 만약 4개의 숫자를 비교해야 하는 경우라면 쓸 법함, 여기서는 숫자 3개만 비교하면 되기 때문에 for문 하나로 숫자 하나 선택하고 나머지 2개는 투포인터로 선택하면 된다.
• 숫자를 하나 선택하고 나머지 두 수는 s, e로 배열의 양끝을 가리키고 시작한다.
• 만약 두 수의 합(std[s] + std[3])+ 선택한 값(target) > 0
  • 두 수의 합의 크기를 줄여야 하므로 e-=1;
• 두 수의 합(std[s] + std[3])+ 선택한 값(target) < 0
  • 두 수의 합의 크기를 늘려야 하므로 s+=1;
• 같을 경우 ⇒ 여기서 중요 ⭐
  • 먼저 i < s 인 경우에만 카운트를 해야한다.
    • s가 i보다 앞에 있다면 이건 이전에 이미 계산된 친구를 또 계산하게 되기때문이다.
      • 예를들어, -5 … 2…. 3이 있다고 하자.
      • i(target값)이 -5를 가리키고, s가 2, e가 3을 가리키는 경우 → 합이 0이 되므로 카운트 된다.
      • 그러다가 target값(i)가 2를 가리키고, s가 -5를 가리킨다고 할 때, e는 또 3을 가리킨다. → 즉, 이미 계산된 걸 또 계산하는 상황이 발생
    • 숫자는 총 3개로 제한되므로 target값 제외 한숫자가 정해지면 나머지 한 숫자도 자동으로 정해진다 ⇒ 이 점을 생각했다.
  • 그 다음, 두 가지 케이스를 고려해야한다.
    • 첫 번째 케이스 : target 값이 -5일경우
      • 학생의 실력이 22333 이런식으로 나열되어있다고 하자
      • s가 2를 가리키고 e가 3을 가리킨 상황일 때,
      • 여기서 나올 수 있는 경우의 수는 2의 개수 * 3의 개수가 된다.
        • 이 부분을 구현하기 위해 각각의 개수를 카운트하는 sCnt, eCnt를 만듦
        • 세 수의 합이 0이 되는 지점까지 s를 하나씩 뒤로 민다. ⇒ 즉, 2가 아닌 지점까지 민다는 뜻
          

          int sCnt = 1;
          while (s + 1 <= te && std[s + 1] + std[e] + target == 0) {
              sCnt++;
              s++;
          }
          ​

        • 마찬가지로 세 수의 합이 0이 되는 지점까지 e를 앞으로 당긴다 ⇒ 3이 아닌 지점까지 당김
          

          int eCnt = 1;
          while (ts < e - 1 && std[s - 1] + std[e - 1] + target == 0) {
              eCnt++;
              e--;
          }
          e--;
          ​

        • 그러면서 각각 sCnt, eCnt로 2와 3의 개수를 같이 세준다.
        • 이때, s와 e의 값이 바뀌는 것을 볼 수 있는데 ⇒ 그 다음에 보면 알 수 있듯이 s와 e의 초기값이 필요하기 때문에 ts, te변수에 미리 s와 e의 초기값을 담아주고 시작했다.
    • 두 번째 케이스 : target 값이 -10일 경우
      • 학생의 실력이 5555555로 주어진 경우
      • s와 e모두 같은 숫자 5를 가리키게 된다.
      • 그러나 위 첫번째 케이스처럼 풀 경우 7*6이 된다.
        • 중복으로 카운트가 되는 문제가 생김 → 이건 직접 손으로 그려보면 알 수 있음
        • 그렇기 때문에 2로 한번 나눠줘야 한다.
        ⇒ 결국, 조합 nC2인 걸 알 수 있음
    • 그래서 최종적으로 두 가지 케이스로 나눠서 카운트를 더해주었다.
      

      if (std[ts] != std[te]) {
          answer += (long) sCnt * eCnt;
      } else {
          answer += (long) sCnt * eCnt / 2;
      }
      ​

코드

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

//

/*
    학생의 코딩 실력 -10000부터 10000사이로 주어질 때, 합이 0이되는 3인조를 만들 수 있는 경우의 수 구하기
    학생수는 최대 10000명까지 가능하다
 */

public class Main {


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

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

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

        Arrays.sort(std);

        int s, e, ts, te, sum, target;
        long answer = 0;
        for (int i = 0; i < N; i++) {
            target = std[i];

            s = 0;
            e = N - 1;
            while (s < e) {
                sum = std[s] + std[e];

                if (s == i) {
                    s++;
                    continue;
                } else if (e == i) {
                    e--;
                    continue;
                }

                if (target + sum == 0) {
                    if (s > i) {
                        ts = s;
                        te = e;

                        int sCnt = 1;
                        while (s + 1 <= te && std[s + 1] + std[e] + target == 0) {
                            sCnt++;
                            s++;
                        }
                        s++;

                        int eCnt = 1;
                        while (ts < e - 1 && std[s - 1] + std[e - 1] + target == 0) {
                            eCnt++;
                            e--;
                        }
                        e--;

                        if (std[ts] != std[te]) {
                            answer += (long) sCnt * eCnt;
                        } else {
                            answer += (long) sCnt * eCnt / 2;
                        }
                    } else {
                        s++;
                    }
                } else if (target + sum > 0) {
                    e--;
                } else {
                    s++;
                }
            }
        }

        System.out.println(answer);

        br.close();
    }
}

 

 

알고리즘 문제) BOJ 3987. 보이저 1호

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

문제 요약

• N*M크기의 항성계가 있다.
• 시그널은 블랙홀(C)를 만나거나 항성계범위를 벗어날때까지 계속 전파된다.
• 만약, 행성(/, \)을 만나면 아래와 같이 반사 된다
  

  

• 인접한 칸으로 한 칸 이동하는데 1초가 걸린다.
• 어느 방향으로 시그널을 보내야 이동 시간이 최대가 되는지 구하여라

시간 제한

• 1초

입력

• N과 M (1~500)
• 다음 줄부터 맵이 주어짐(.는 빈칸)
• 마지막 줄에는 탐사선 위치 PR, PC가 주어짐 (PR:1~N, PC:1~M)

출력

• 시그널을 보내는 방향을 출력(D,L,R,U)
• 만약 여러 가지 존재한다면 순서 중 앞서는 거 출력
• 둘째줄에는 가장 긴 시간을 출력한다.
  • 만약 무한히 전파될 수 있다면 Voyager 출력

접근법

• 구현 문제라 문제에 주어진대로 직관적으로 풀었다.
• 일단 U, R, D, L → 방향에 우선순위를 부여헀다 → 가장 앞서는 것을 출력하라 했으므로
• 그리고 그에 맞게 delR, delC 델타 배열을 만들었다.
• move함수에 현재 보이저의 위치(PR,PC)와 쏜 방향(CD)를 매개변수로 보냈다.
  • move함수는 보이저가 이동한 시간 time을 반환한다.
  • mr, mc는 현재 위치에서 한칸 이동한 위치를 나타내고, 그 위치가 경계를 벗어나거나 블랙홀을 만날 경우 while문을 빠져나가게 했다.
  • 만약 행성을 만날경우 방향을 바꿔주었다.
  • 그리고 현재 위치 cr, cc를 mr, mc로 바꿔주고, 시간을 1씩 늘렸다.
  • 무한히 항해하는 걸 판단하는 방법은 → 시간이 전체 항성계 칸 개수 * 2가 되면 무한히 항해한다고 판단해서 시간을 -1로 설정하고 while문을 빠져나갔다.
• move함수 리턴값이 -1일경우 → Voyage를 출력하도록 함

코드

//55 분

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

public class Main {
    static int N, M;
    static char[][] map = new char[510][510];
    static int[] delR = {-1, 0, 1, 0};
    static int[] delC = {0, 1, 0, -1};
    static char[] dir = {'U', 'R', 'D', 'L'};

    static int move(int PR, int PC, int CD) {
        int time = 1;

        int cr = PR, cc = PC, mr, mc;
        while (true) {
            mr = cr + delR[CD];
            mc = cc + delC[CD];

            if (mr < 0 || mc < 0 || N <= mr || M <= mc || map[mr][mc] == 'C') break;

            if (time == N * M * 2) {
                // 이미 방문한 곳 또 방문하면 -> 무한히 전파
                time = -1;
                break;
            }

            cr = mr;
            cc = mc;

            if (map[mr][mc] == '/')  CD = CD % 2 == 0 ? CD + 1 : CD - 1;
            else if (map[mr][mc] == '\\')  CD = 3 - CD;

            time++;
        }

        return time;
    }
    public static int[] solution(int PR, int PC){
        int[] answer = {0,-1};
        int ret;

        for (int i = 0; i < 4; i++) {
            // 현재 방향 i인덱스를 매개변수로 넘김
            ret = move(PR, PC, i);

            if (ret == -1) {
                answer[0] = ret;
                answer[1] = i;
                break;
            } else if (ret > answer[0]) {
                answer[0] = ret;
                answer[1] = i;
            }
        }

        return answer;
    }

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

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        String input;
        for (int i = 0; i < N; i++) {
            input = br.readLine();

            for (int j = 0; j < M; j++) {
                map[i][j] = input.charAt(j);
            }
        }

        st = new StringTokenizer(br.readLine());
        int PR = Integer.parseInt(st.nextToken()) - 1;
        int PC = Integer.parseInt(st.nextToken()) - 1;

        int[] ans = solution(PR, PC);

        System.out.println(dir[ans[1]]);
        if (ans[0] == -1) System.out.println("Voyager");
        else System.out.println(ans[0]);

        br.close();
    }
}