📙[Algo] 24.03.12 알고리즘

알고리즘 문제) BOJ 1695. 팰린드롬 만들기

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

문제 요약

• 팰린드롬 : 앞에서보나 뒤에서보나 같은 수열
• 순열이 주어졌을 때 최소 개수의 수를 끼워넣어 팰린드롬을 만들려고 함
  • 최소 몇 개의 수를 끼워 넣으면 될까?

시간 제한

• 2초

입력

• 수열 길이 N
  • 1≤N≤5000
• N개의 수열을 이루는 수들이 주어짐
  • int범위 내

출력

• 끼워 넣을 수 있는 수들의 최소 개수

접근법

1. 완전탐색으로 생각하기
   • 일단 이미 적혀있는 수들 내에서만 끼워 넣어야 한다.
   • 팰린드롬 ⇒ 가운데를 기준으로 좌우대칭일 것!
   • 즉, 숫자들 중 하나를 가운데 기준점으로 잡고 좌우대칭 만들어가면서,
   • 추가하는 숫자의 최소 개수로 갱신….
   • 맨 앞 수, 맨 끝 수를 비교하며 동일한지 체크하기
     • s : 0, e : N-1
       • arr[s] == arr[e]
         • s++, e—
       • arr[s] ≠ arr[e]
         • s뒤에 arr[e]추가
         • e앞에 arr[s]추가
       ⇒ 즉 추가하는 위치에 따라 최소 개수가 정해진다,,

코드

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

public class Main {
    static int N;
    static int[] nums;
//    static int answer = 1 << 30;

    static int[][] dp;

    // 1. 백트랙킹
//    static void recur(int s, int e, int cnt) {
//
//        if (s == e) {
//            answer = Math.min(answer, cnt);
//            return;
//        }
//
//        if (nums[s] == nums[e]) {
//            recur(s + 1, e - 1, cnt);
//        } else {
//            recur(s, e - 1, cnt + 1);   // arr[s]뒤에 nums[e]값 추가
//            recur(s + 1, e, cnt + 1);   // arr[e]앞에 nums[s]값 추가
//        }
//
//    }

    // 2. 함수 + 메모이제이션 적용하기
    static int recur(int s, int e) {

        if (s >= e) return 0;

        if (dp[s][e] != -1) return dp[s][e];

        int ret = 1 << 30;
        if (nums[s] == nums[e]) {
            ret = Math.min(ret, recur(s + 1, e - 1));
        } else {
            ret = Math.min(ret, recur(s, e - 1) + 1);   // arr[s]뒤에 nums[e]값 추가
            ret = Math.min(ret, recur(s + 1, e) + 1);   // arr[e]앞에 nums[s]값 추가
        }

        dp[s][e] = ret;
        return dp[s][e];
    }

    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;

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

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

//        recur(0, N - 1, 0);

        dp = new int[5010][5010];
        for (int i = 0; i < 5010; i++) {
            Arrays.fill(dp[i], -1);
        }

        bw.write(String.valueOf(recur(0, N - 1)));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 10942. 팰린드롬?

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

문제 요약

• 홍준이가 자연수 N개를 적고 홍준이에게 M개 질문함
• 각 질문은 두 정수 S, E로 나타내며, S번째 수부터 E번째까지 팰린드롬인지 묻기
• 자연수 N개와 질문 M개가 모두 주어졌을 때, 명우의 대답 구하기

시간 제한

• 자바 2.5초

입력

• 수열의 크기 N
  • 1≤N≤2000
• 홍준이가 적은 N개의 수가 주어짐
• 질문 개수 M
  • 1≤M>≤100만
• M개의 줄에 질문이 주어지며, S, E가 한줄에주어짐

출력

• 각 질문에 대해 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력

접근법

팰린드롬 판별

1. 길이 1 : 팰린드롬
2. 길이 2 : 팰린드롬 X
3. 길이 3이상
   • 좌우 대칭 비교…!

넘넘 간단했던 문제;;

그냥 양끝단 비교하면서 아닌 순간 발견되면 return 0;

그게아니면 계속 이동할 테니 s≥e 되면 return 1

⇒ 이걸 dp에 기록해서 또 써먹으면 됨

코드

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

public class Main {
    static int N, M;
    static int[] arr;
    static int[][] queries;
    static int[][] dp;

    static int recur(int s, int e) {

        if (s >= e) return 1;

        if (dp[s][e] != -1) return dp[s][e];

        if (arr[s] != arr[e]) return 0;

        int ret = recur(s + 1, e - 1);

        dp[s][e] = ret;
        return dp[s][e];
    }

    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;

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

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

        M = Integer.parseInt(br.readLine());
        queries = new int[M][2];
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            queries[i][0] = Integer.parseInt(st.nextToken());
            queries[i][1] = Integer.parseInt(st.nextToken());
        }

        dp = new int[2010][2010];
        for (int i = 0; i < 2010; i++) {
            Arrays.fill(dp[i], -1);
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
            sb.append(recur(queries[i][0], queries[i][1])+"\\n");
        }

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

 

알고리즘 문제) BOJ 1937. 욕심쟁이 판다

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

문제 요약

• n*n 크기 대나무 숲
• 대나무를(칸에 적힌 대나무 개수) 다 먹으면서 상하좌우 이동
  • 단, 그 전 지역보다 대나무가 많은 곳으로 이동
• 어떤 지점에서 시작하고 어떤 곳으로 이동해야 최대한 많은 칸을 방문할 수 있는지 구하기

시간 제한

• 2초

입력

• 대나무 숲 크기 n
  • 1≤n≤500
• 대나무 숲 정보가 주어진다.
  • 대나무 양이 정수값으로 주어짐
  • 100만보다 작거나 같은 자연수

출력

• 이동할 수 있는 칸의 수의 최댓값 출력

접근법

1. 조건
   • 상하좌우로 이동
   • 현재 칸보다 숫자가 더 큰 칸으로 이동
2. 완전 탐색으로 생각하기(백트랙킹)
   • (0,0)부터 (N-1,N-1)까지 모든 칸을 시작점으로 recur 돌리기
   • 종료 조건은 더 이상 상하좌우로 이동할 수 없을 때

// 1.백트랙킹으로 생각하기
  static void recur(int row, int col, int total) {

      // 종료 조건은 더이상 상하좌우로 이동할 수 없을 때
      if (!check(row, col)) {
          answer = Math.max(answer, total);
          return;
      }

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

          if (!borderCheck(mrow, mcol) || map[row][col] >= map[mrow][mcol]) continue;

          recur(mrow, mcol, total + 1);
      }

  }

코드

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

public class Main {
    static int N; // 숲 크기
    static int[][] map; // 숲 정보
    static int[] delR = {-1, 1, 0, 0}; // 행 이동 : 상하좌우
    static int[] delC = {0, 0, -1, 1}; // 열 이동 : 상하좌우
    static int[][] dp;
    static int answer; // 경로 개수

    // 경계 체크
    static boolean borderCheck(int row, int col) {
        return 0 <= row && 0 <= col && row < N && col < N;
    }

    // 이동할 곳이 있는지
    static boolean check(int row, int col) {

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

            if (!borderCheck(mrow, mcol)) continue;

            if (map[row][col] < map[mrow][mcol]) cnt++;
        }

        if (cnt == 0) return false;
        else return true;
    }

    // 1.백트랙킹으로 생각하기
//    static void recur(int row, int col, int total) {
//
//        // 종료 조건은 더이상 상하좌우로 이동할 수 없을 때
//        if (!check(row, col)) {
//            answer = Math.max(answer, total);
//            return;
//        }
//
//        int mrow, mcol;
//        for (int dir = 0; dir < 4; dir++) {
//            mrow = row + delR[dir];
//            mcol = col + delC[dir];
//
//            if (!borderCheck(mrow, mcol) || map[row][col] >= map[mrow][mcol]) continue;
//
//            recur(mrow, mcol, total + 1);
//        }
//
//    }

    // 2. 메모이제이션 + 함수적용 : 최대 칸을 방문하는 경우를 반환
    static int recur(int row, int col) {

        // 종료 조건은 더이상 상하좌우로 이동할 수 없을 때
        if (!check(row, col)) return 0;

        if (dp[row][col] != -1) return dp[row][col];

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

            if (!borderCheck(mrow, mcol) || map[row][col] >= map[mrow][mcol]) continue;

            ret = Math.max(ret, recur(mrow, mcol) + 1);
        }

        dp[row][col] = ret;
        return dp[row][col];
    }

    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;

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

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

        dp = new int[510][510];
        for (int i = 0; i < 510; i++) {
            Arrays.fill(dp[i], -1);
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                answer = Math.max(answer, recur(i, j) + 1);
            }
        }

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