풀이

• 1~N개의 풍선이 원형으로 놓여있다.
  • i번 풍선의 오른쪽에는 i+1번 풍선이, 왼쪽에는 i-1번 풍선이 있다.
• 제일 처음에 1번 풍선 터뜨린다. 다음에는 풍선 안에 있는 종이를 꺼내어, 그 종이에 적혀있는 값만큼 이동한다. 양수일 때는 오른쪽, 음수일때는 왼쪽.
• 예를 들어, [3,2,1,-3,-1] 이 적혀있으면, 3이 적혀있는 1번 풍선 -> -3이 적혀 있는 4번 풍선 -> -1이 적혀 있는 5번 풍선 -> 1이 적혀 있는 3번 풍선-> 2가 적혀있는 2번 풍선 순으로 터진다.
• 원형큐면 덱으로 풀자. 덱을 몰랐더니 오래 걸림.. 하지만 덱을 안다면? 10분컷 쌉가능
  • 양수가 나왔어? 그러면 앞에 N개를 뽑아서 뒤에 순서대로 넣으면 됨.
    • deq.offer(deq.poll())
  • 음수가 나왔어? 그러면 뒤에 N개를 뽑아서 앞에 순서대로 넣으면 됨.
    • deq.offerFirst(dq.pollLast())

🙆‍♀️ 정답 풀이

import java.util.*;
import  java.io.*;
public class BOJ2346 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        Deque<int[]> queue = new ArrayDeque<>();
        StringTokenizer st= new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        for(int i=0;i<N;i++){
            int num =  Integer.parseInt(st.nextToken());
            queue.offer(new int[]{num,i+1});
            arr[i] = num;
        }
        StringBuilder sb = new StringBuilder();
        int[] first = queue.poll();   //첫번째꺼 빼기
        sb.append(first[1]+" ");
        int cnt = first[0];
        while(!queue.isEmpty()){
            if(cnt>0){
                for(int k=1;k<cnt;k++){
                    queue.add(queue.poll());
                }
                int[] nxt = queue.poll();// 앞에꺼 빼기
                cnt= nxt[0];
                sb.append(nxt[1]+" ");
            }
            else{
                for(int k=1;k<-cnt;k++){
                    queue.addFirst(queue.pollLast());
                }
                //뒤에꺼 빼기
                int[] nxt = queue.pollLast();
                cnt = nxt[0];
                sb.append(nxt[1]+" ");
            }
        }
        System.out.println(sb);
    }
}

풀이

• 그놈의 디피... 용기를 내서 도전해보았다.
• 반복문을 사용하는 bottom-up 방식을 이용.
• dp[0][i] or dp[1][i] : 이 칸 까지의 최대 값 저장하는 공간. 처음엔 dp 1차원 배열로도 가능한가? 생각했지만 현재 내가 0행 칸을 보고 있는지 1행 칸을 보고 있는지에 따라 메모이제이션 방식이 달라지기 때문에 2차원 배열로 구현했다.
• 만약 0행 칸을 보고 있는 경우, 대각선 왼쪽 아래 칸+ 현재 칸 을 선택한 경우와 내 바로 왼쪽 칸을 선택하고 현재 칸은 선택하지 않은 경우 중 큰 값을 비교하여 메모해주면 된다.

🙆‍♀️ 정답 코드

import java.util.*;
import java.io.*;
public class BOJ9465 {
    public static void main(String[] args) throws Exception{
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for(int i=0;i<T;i++){
            int n = Integer.parseInt(br.readLine());
            int[][] map = new int[2][n+1];
            int[][] dp = new int[2][n+1];
            StringTokenizer st;
            for(int j=0;j<2;j++){
                st = new StringTokenizer(br.readLine());
                for(int m=0;m<n;m++){
                    map[j][m] = Integer.parseInt(st.nextToken());
                }
            }
            dp[0][0] = map[0][0];
            dp[1][0] = map[1][0];
            for(int k=1;k<n;k++){
                dp[0][k] = Math.max(dp[1][k-1]+map[0][k],dp[0][k-1]);
                dp[1][k] = Math.max(dp[0][k-1]+map[1][k],dp[1][k-1]);
            }
            System.out.println(Math.max(dp[0][n-1],dp[1][n-1]));
        }
    }
}

풀이

• 2^N*2^N 2차원 배열을 Z모양으로 탐색.
• N이 주어졌을 때, r행 c열을 몇번째로 방문하는지 출력.
• 앞서 풀었던 쿼드트리, 종이의 개수랑 똑같이 풀었는데 시간 초과 났다.
• 핵심은 4등분을 하면서 r행 c열이 1,2,3,4사분면 중 어디에 있는지를 파악하며 그 부분만 패면 된다.

정답 풀이

import java.util.*;
import java.io.*;
public class Main {
    static int N,r,c;
    static int[][] map;
    static int cnt = 0;
    static int answer = 0;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int m = Integer.parseInt(st.nextToken());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        int N = (int)Math.pow(2,m);
        cur(N,0,0);
    }
    private static void cur(int n,int i, int j){
        //크기가 1이 되면
        if(n==1){
            System.out.println(answer);
            return;
        }
        int newSize = n/2;
        if(r<i+newSize && c<j+newSize){
            //1사분면
            cur(newSize,i,j);
        }
        //2사분면
        if(r<i+newSize && c>=j+newSize){
            answer+=(n*n)/4;
            cur(newSize,i,j+newSize);
        }
        //3사분면
        if(r>=i+newSize && c<j+newSize){
            answer+=((n*n)/4)*2;
            cur(newSize,i+newSize,j);
        }
        if(r>=i+newSize && c>=j+newSize){
            answer+=((n*n)/4)*3;
            cur(newSize,i+newSize,j+newSize);
        }
    }
}
>```
>  - 여기서 각 사분면에 `answer` 구하는 방식이 처음에 이해가 안갔는데, 위 사진에서 4등분했을 때 0,16,32,48이 각 사분면의 시작점이다. 여기서 공식을 구해낸 것. 2사분면이면 `(8*8)/4 = 16`, 3사분면이면 `((8*8)/4)*2` ...
- 그러다가 r행 c열을 구하게 되는 곳은 size가 1인 곳을 만났을 때다.  그래서  `if(n==1) ` 에서 answer를 출력하는 것!

- 시간초과를 해결하지 못해서 풀이를 봤던 문제다. 분할 정복 어려워. . .🤯

풀이

• 주어진 영상이 모두 0이 되거나 1로 되어 있으면 "0", "1"로 압축할 수 있고, 그게 아니라면 4등분하여 압축을 반복한다.

• 1708 종이의 개수랑 거의 똑같은 문제인데, 4등분 시도 하기 전에 "("를 넣어주고, 끝날 때 ")"를 넣어줘야 한다는 부분이 다름.

  정답 풀이

  import java.util.*;
  import java.io.*;
  public class Main {
    static int[][] map;
    static StringBuilder sb;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N =  Integer.parseInt(br.readLine());
        map = new int[N][N];
        for(int i=0;i<N;i++){
            String str = br.readLine();
            String[] arr = str.split("");
            for(int j=0;j<N;j++){
                map[i][j] = Integer.parseInt(arr[j]);
            }
        }
        sb = new StringBuilder();
        cur(N,0,0);
        System.out.println(sb);
    }
    private static void cur(int n,int i, int j){
        //같은수로만 이루어졌는지 확인
        boolean isFind = true;
        int start = map[i][j];
        L:for(int l=i;l<i+n;l++){
            for(int m=j;m<j+n;m++){
                if(start!=map[l][m]){
                    isFind = false;
                    break L;
                }
            }
        }
        if(!isFind){
            //왼위,오위,왼아,오아
            int newSize = n/2;
            sb.append("(");
            cur(newSize,i,j);
            cur(newSize,i,j+newSize);
            cur(newSize,i+newSize,j);
            cur(newSize,i+newSize,j+newSize);
            sb.append(")");
        }
        else{
            //같은거로만 이루어짐
            sb.append(start);
        }
    }
  }

• 종이의 개수 문제와 로직이 똑같다.

풀이

• -1,0,1 로 채워져 있는데, 종이가 모두 같은 수로 되어 있지 않으면, 같은 크기의 종이 9개 로 자르고, 잘린 종이에 대해 종이가 모두 같은 수로 이루어질 때 까지 반복한다.
• -1로만 채워진 종이 개수, 0으로만, 1로만 채워진 종이개수 각각 구해라.
• 재귀함수를 써야 겠다고 생각. 일단 색이 다 같은지 확인하고, 다 같지 않다면! 9등분으로 나눈 부분등을 하나씩 재귀를 돌린다. 이 때, 9등분이므로 사이즈는 지금사이즈/3 으로 줄어들게 된다.

정답 풀이

```java import java.util.; import java.io.; public class Main { static int zeroA = 0,oneA=0,minuA=0; static int N; static int[][] map; public static void main(String[] args)throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); N = Integer.parseInt(br.readLine()); map = new int[N][N]; StringTokenizer st; 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()); } } cur(N,0,0); System.out.println(minuA); System.out.println(zeroA); System.out.println(oneA); } private static void cur(int k,int i, int j){ //색이 다 같으면 boolean isFind = true; int start = map[i][j]; L:for(int l=i;l<i+k;l++){ for(int m=j;m<j+k;m++){ if(start!=map[l][m]){ isFind = false; break L; } } } if(!isFind){ //다 같지 않으면 int newSize = k/3; //9개 recusive cur(newSize,i,j); cur(newSize,i,j+newSize); cur(newSize,i,j+newSize2); cur(newSize,i+newSize,j); cur(newSize,i+newSize,j+newSize); cur(newSize,i+newSize,j+newSize2); cur(newSize,i+newSize2,j); cur(newSize,i+newSize2,j+newSize); cur(newSize,i+newSize2,j+newSize2); } else{ if(start==0) zeroA++; else if(start==1) oneA++; else minuA++; } } }

• 나는 처음에 이렇게 재귀를 안돌리고, 2중 for문으로 돌렸는데 사실 똑같긴하다. 이런식으로. 아무튼 저 코드 방식으로 재귀 돌리는 문제가 분할정복에 꽤 많이 등장하는 거 같다. 익혀두기!!

풀이

• A,B,C의 범위가 2,147,483,647 이하의 자연수 라서, 냅다 곱하고 나누고 하면 메모리초과 난다.

• 모듈러 성질, 지수 법칙을 이용하면 된다.

  • 모듈러 성질 : (a*b) % C = (a%c * b%c) % c
  • 지수 법칙 :a^(n+m) = a^n*a*m

• 그리고 중요한 것, B(=지수)가 홀수인지 짝수인지에 따라 다르게 return 한다.

• 또 중요한 것, long 타입으로 a,b,c를 받아야 에러가 안터진다.

정답 풀이

```java import java.util.; import java.io.; public class Main { public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); long A = Integer.parseInt(st.nextToken()); long B = Integer.parseInt(st.nextToken()); long C = Integer.parseInt(st.nextToken()); // (A^B)%C System.out.println(cur(A,B,C)); } private static long cur(long a,long b,long c){ // b가 1이 되면 a^1 이므로 return a%c if(b==1){ return a%c; } long res = cur(a,b/2,c); if(b%2==1) return (resres%c)a%c; return res*res%c; } }

```

풀이

• 멀티탭 구멍의 개수 N, 전기 용품의 총 사용횟수 K.
• 전기 용품 이름이 K 이하의 자연수로 사용순서대로 주어진다.
• 하나씩 플러그를 빼는 최소의 횟수를 구해라.
• 예를 들어, 2 3 2 3 1 2 7 이 사용순서라면, 제일 나중에 쓰거나 아예 안쓴 애를 멀티탭에서 제거해야겠다! 라고 생각 했음.
• 그럼 얘를 나중에 쓴다는걸 어떻게 알지...? 라는 생각에 HashMap에 저장해야겠다고 생각.
  • HashMap<Integer, LinkedList<Integer>> 를 만들어서, key는 입력받는 전기용품의 이름(2,3...) , value는 그 전기용품이 등장하는 idx를 List로 저장하고, 오름차순 정렬했다. 위 예시에서는, key=2, List={0,2,6} 이런식으로 저장한 꼴.
• 그다음, 전기용품 입력받은 배열을 순회하는데, 현재 멀티탭 구멍의 개수보다 꽂힌 전기용품 개수가 적고, 아직 꽂힌적 없는 전기용품인 경우 multitab 리스트에 offer했다.
• 만약 이미 전기용품 꽂혀져 있으면,(멀티탭 리스트에 존재하면) continue,
• 전기용품이 N개 다 꽂혀있으면, 이제 제일 나중에 나올 전기용품 아니면 안나올 전기용품을 multitab 리스트에서 제거해야 한다.
  • 현재 보고 있는 전기용품 배열의 인덱스 이후로 꽂아야 하는 전기용품들을 hashmap에서 탐색하여 후보로 저장.
  • 후보들 순회하면서, 가장 나중에 나오는 전기용품 후보를 찾아서 multitab 리스트에서 제거한다. 그리고 multab에 이제 꽂아야 하는 전기용품을 추가.
  • 제거하는 횟수를 세야하니까, 이 때 answer++

🙆‍♀️ 정답 풀이

import java.util.*;
import java.io.*;
public class BOJ1700 {
    public static void main(String[] args) throws Exception{
        HashMap<Integer,LinkedList<Integer>> map = new HashMap<>();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int[] arr = new int[K];
        for(int i=0;i<K;i++){
            int key =Integer.parseInt(st.nextToken());
            arr[i] = key;
            LinkedList<Integer> idxQueue;
            if(map.containsKey(key)){
                idxQueue = map.get(key);
                idxQueue.offer(i);
                Collections.sort(idxQueue); //오름차순 정렬
                map.put(key,idxQueue);
            }
            else{
                idxQueue= new LinkedList<>();
                idxQueue.offer(i);
                map.put(key,idxQueue);
            }
        }
        //멀티탭 꽂을거
        LinkedList<Integer> multitab = new LinkedList<>();
        int ans = 0;
        for(int i=0;i<K;i++){
            if(multitab.contains(arr[i])) continue;
            if(multitab.size()==N){
                int[] delArr = new int[multitab.size()];       //i 인덱스 이후에 나오는 idx 넣기
                Arrays.fill(delArr,-1);
                boolean isFind= false;                          //i 인덱스 이후가 아예 없다면, 얘가 빠지면 됨 그래서 break
                int delIdx = -1;                                //얘가 빠져야 할 경우, idx 저장하려고 만든 변수
                for(int s=0;s<multitab.size();s++){
                    int idx = multitab.get(s);
                    LinkedList<Integer> idxList = map.get(idx);     //해당 제품이 등장하는 인덱스 리스트
                    int temp = -1;
                    for(int m=0;m<idxList.size();m++){
                        if(idxList.get(m)>i){
                            temp = idxList.get(m);                  // i 보다 큰 idx에서 해당 제품이 나오는 경우, 삭제 후보이므로 temp에 저장
                            break;
                        }
                    }
                    if(temp==-1){
                        delIdx = s;
                        isFind = true;
                        break;
                    }
                    else{
                        delArr[s] = temp;                      //삭제 후보 tempArr에 저장
                    }
                }
                if(isFind) {
                    // i 이후로 등장하지 않아서 바로 삭제하면 되는 경우
                    multitab.remove(delIdx);
                    multitab.offer(arr[i]);
                }
                else{
                    // 삭제 후보들 돌면서, 가장 큰 애를 찾으면 됨.(가장 나중에 나온다는 거기 때문에)
                    int maxVal = -1;
                    int maxIdx = -1;
                    for(int a=0;a<delArr.length;a++){
                        if(delArr[a]>maxVal) {
                            maxVal = delArr[a];
                            maxIdx = a;
                        }
                    }
                    //가장 나중에 나오는 애를 찾아서 지우고 해당 arr[i] 를 넣어주기
                    multitab.remove(maxIdx);
                    multitab.offer(arr[i]);
                }
                ans++;
            }
            else if(multitab.size()<N){
                multitab.offer(arr[i]);
            }
        }
        System.out.println(ans);
    }
}

• 코드가 꽤 긴데,,, 그래두 내 힘으로 풀었다. !! 작년 알고리즘 스터디 때 못풀어서 포기했던 문젠데...😁

• 다른 사람 코드를 보니까, hashmap 쓸 필요 없이 그냥 List만 이용해서 멀티탭에서 제거할 우선순위를 구할 수 있다. 나랑 로직은 같은데 난 좀 복잡하게 푼거 같은....

풀이

• S[i]에 시작해서 T[i]에 끝나는 N개의 수업이 주어진다. 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 함.

• 앞서 풀었던 회의실 배정 문제랑 비슷한 듯 하지만, 모든 수업을 가능해야 한다 라는 조건이 다르다.

• 이 조건 때문에, 2차원 배열로 시작시간, 끝나는 시간을 담고 시작하는 시간이 빠른 순으로 정렬을 해준다. (Comparator 사용)

• 그 다음 우선순위 큐를 이용하는데, 우선순위 큐에는 회의가 끝나는 시간을 넣을 것이다.

  • 우선순위 큐를 이용하는 이유는, 회의가 끝나는 시간들을 넣었을 때 빨리 끝나는 순으로 poll 할 수 있도록 정렬이 되기 때문에 사용한다.

• 배열의 첫번째 원소의 끝나는 시간을 넣고 시작한다. for문을 순회하면서, 배열의 원소의 시작 시간이 우선순위 큐의 peek 한 원소 보다 늦으면(크면), 같은 강의실에서 할 수 있으므로, 끝나는 시간을 갱신할 수 있다.

  • 우선순위 큐에서 poll하고, 지금 보고 있던 배열 원소의 끝나는 시간을 넣어준다.

• peek한 원소보다 현재 보고 있는 배열 원소의 시작 시간이 작다면, peek한 원소와 같은 회의실에서 진행할 수 없으므로 끝나는 시간을 갱신할 수 없다.(=다른 회의실에서 진행해야 함.)

  • 우선순위 큐에 지금 보고 있던 배열 원소의 끝나는 시간을 offer.

• for문으로 배열을 다 순회한 뒤, 우선순위큐 size를 구하면 그것이 정답(=필요한 회의실 수)

🙆‍♀️ 정답 코드

```java import java.util.; import java.io.; public class Main { public static void main(String[] args) throws Exception{ BufferedReader br =new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); int[][] arr = new int[N][2]; StringTokenizer st; for(int i=0;i<N;i++){ st = new StringTokenizer(br.readLine()); arr[i][0] = Integer.parseInt(st.nextToken()); arr[i][1] = Integer.parseInt(st.nextToken()); } Arrays.sort(arr,new Comparator<int[]>(){ @Override public int compare(int[] o1, int[] o2){ if(o1[0]==o2[0]) return Integer.compare(o1[1],o2[1]); return Integer.compare(o1[0],o2[0]); } }); PriorityQueue pq = new PriorityQueue<>(); pq.add(arr[0][1]); for(int i=1;i<N;i++){ if(arr[i][0]>=pq.peek()){ pq.poll(); pq.offer(arr[i][1]); } else{ pq.offer(arr[i][1]); } } System.out.println(pq.size()); } }

• 우선순위큐를 생각도 못해서 너무 어려웠다. 다음에 다시 풀어보zr 🤧

풀이

• 캠핑장은 연속하는 P일 중 L일 동안만 사용할 수 있고, 강산이가 V일짜리 휴가를 시작했을 때 강산이가 캠핑장을 최대 며칠동안 사용할 수 있는가?

• 어쨌든 사용할 수 있는 일수만큼 연속해서 사용하는 경우가 최대 사용할 수 있다.

• V를 P로 나누고, 그 값에 L을 곱한다. 이게 일단 나머지 없이 최대로 캠핑할 수 있는 날짜수.

  • 예를 들어, L=5, P=8, V=20 이면 OOOOOXXXOOOOOXXX 까지 나타낸 경우.

• 그 뒤에도 V를 P로 나눈 나머지를 구하고, 이게 위에서 구하고 남은 날짜 보다 크면 L을 더해주고, 그게 아니면 나머지를 더해준다.

• 위에서 V/P*L = 10 이고, 나머지 휴가가 20-16=4 남은 상황. 이것이 V%P=4 와 같고, 이 값이 L보다 작으므로 답은 (V/P*L) +(V%P)

🙆‍♀️ 정답 코드

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args)throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input;
        int cnt = 0;
        while(true){
            cnt++;
            input = br.readLine();
            if(input.equals("0 0 0")) break;
            else{
                StringTokenizer st = new StringTokenizer(input);
                int L = Integer.parseInt(st.nextToken());
                int P = Integer.parseInt(st.nextToken());
                int V = Integer.parseInt(st.nextToken());
                int div = V/P;
                int nam = V%P;
                //2 4 6
                //OOXXOO
                if(nam>L) nam = L;
                int ans = div*L+nam;
                System.out.println("Case "+cnt+": "+ans);
            }
        }
    }
}

풀이

• 한 개의 회의실이 있고, 사용하고자 하는 N개의 회의가 있다.
• 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아라.
• 각 회의가 겹치지 않게, 회의실을 사용할 수 있는 회의의 최대 개수 이므로, 끝나는 시간을 기준으로 회의를 오름차순 정렬을 한다.
• Comparator 를 이용해서, 끝나는 시간이 같을 경우 시작 시간이 빠른 순으로 정렬한다.
• 그리고 나서, for문으로 순회하면서 차례대로 시작시간이 지금 기준이 되는 끝나는 시간보다 늦으면, cnt를 늘리고, 기준 끝나는 시간을 갱신한다.

🙆‍♀️ 정답 풀이

```java import java.util.; import java.io.; public class Main { public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); int[][] arr = new int[N][2]; StringTokenizer st; for(int i=0;i<N;i++){ st = new StringTokenizer(br.readLine()); arr[i][0] = Integer.parseInt(st.nextToken()); arr[i][1] = Integer.parseInt(st.nextToken()); } Arrays.sort(arr, new Comparator<int[]>() { @Override public int compare(int[] o1, int[] o2) { if(o1[1] == o2[1]){ return Integer.compare(o1[0],o2[0]); } return Integer.compare(o1[1],o2[1]); } }); int cnt = 1; int start = arr[0][0]; int end = arr[0][1]; for(int idx=1;idx<N;idx++){ if(end<=arr[idx][0]){ cnt++; end = arr[idx][1]; } } System.out.println(cnt); } }

```

풀이

• 준규가 갖고 있는 동전은 N종류, 동전을 적절히 사용해서 합을 K로 만드는데, 필요한 동전 개수의 최솟값을 구해라.
• 전형적인 그리디 문제. 동전 N종류의 큰 값들부터 세면서 K를 만들 수 있는지 확인한다.

🙆‍♀️ 정답 코드

```java import java.util.; import java.io.; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int N = Integer.parseInt(st.nextToken()); int K = Integer.parseInt(st.nextToken()); int[] arr = new int[N + 1]; for (int i = 1; i <= N; i++) { arr[i] = Integer.parseInt(br.readLine()); } int cnt = 0; for(int j=arr.length-1;j>0; j--){ if(arr[j]<=K){ int div = K/arr[j]; cnt+=div; K=K%arr[j]; } } System.out.println(cnt); } }

```

풀이

• 길이가 L인 테이프가 무한개, 테이프로 물을 막을 때, 적어도 그 위치의 0.5만큼 간격을 줘야한다.
• 항승이가 필요한 테이프의 최소 개수를 구해라.
• 만약에 물이 새는 곳 위치가 1 2 100 101, L=2 이렇게 주어지면, 1에서 부터 테이프를 붙여서 1-0.5~ 2+0.5) 범위를 감싸면 조건을 충족시킨게 된다.
• 그래서 일단 주어지는 물새는 곳 위치 배열을 오름차순 정렬한 다음, for문으로 배열을 순회하면서 최댓값 arr[i]+L-0.5 범위 내에 들어오는지 확인하고, 안 들어오면 cnt++ 늘려주고 max값 갱신하여 필요한 테이프 개수를 센다.

정답 풀이

import java.util.*;
import java.io.*;
public class BOJ1449 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int L = Integer.parseInt(st.nextToken());
        int[] arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);
        int cnt = 0;
        double max = -1;
        for(int i=0;i<arr.length;i++) {
            if (arr[i] <= max) continue;
            max = arr[i] + L - 0.5;
            cnt++;
        }
        System.out.println(cnt);
    }
}

풀이

• M*N 크기의 보드. 검은색은 B, 흰색은 W로나타낸다.
• 이것을 잘라서 8*8로 나타내려고 한다.
• 검,흰이 번갈아서 칠해져 있어야 한다.
• 8*8로 잘라냈을 때, 몇 개의 정사각형을 다시 칠해야하는지, 최소 개수를 구해라.
• 8*8로 잘라야 하니까,세로 0~N-8 까지, 가로 M-8까지를 for문으로 돌리면서 시작점을 잡는다.
• 그 시작점부터 8*8 체스판 안을 보는데, 첫번째 줄이 BWBWBWBW 인 경우 랑 WBWBWBWB인 경우 두개가 있어서 이 둘의 경우를 다시 체크해야 하는 애들을 모두 체크한다. 그리고 나서 더 작은 수를 answer로 갱신한다.

정답 풀이

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args)throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        char[][] map = new char[N][M];
        String[] stringMap = new String[N];
        for(int i=0;i<N;i++){
            stringMap[i] = br.readLine();
            map[i] = stringMap[i].toCharArray();
        }
        //8*8만큼 자르기
        int minVal = Integer.MAX_VALUE;
        for(int i=0;i<=N-8;i++){
            for(int j=0;j<=M-8;j++){
                int cnt = 0;
                for(int start=i;start<i+8;start++){
                        char[] temp;
                        if((start-i)%2==0){
                            temp = "BWBWBWBW".toCharArray();
                        }
                        else{
                            temp = "WBWBWBWB".toCharArray();
                        }
                        for(int startj=j;startj<j+8;startj++){
                            if(map[start][startj]!=temp[startj-j]){
                                cnt++;
                            }
                        }
                }
                minVal = Math.min(minVal,cnt);
                cnt = 0;
                    for(int start=i;start<i+8;start++){
                        char[] temp;
                        if((start-i)%2==0){
                            temp = "WBWBWBWB".toCharArray();
                        }
                        else{
                            temp = "BWBWBWBW".toCharArray();
                        }
                        for(int startj=j;startj<j+8;startj++){
                            if(map[start][startj]!=temp[startj-j]){
                                cnt++;
                            }
                        }
                    }
                minVal = Math.min(minVal,cnt);
            }
        }
        System.out.println(minVal);
    }
}
>```

- 다른 풀이를 참고해보니까, 첫줄이 BWBWBWBW인 경우를 구십도 회전한게 WBWBWBWB이 된단다.
- 하나만 계산한 뒤, *2 해주면 답이 된다는 것.

풀이

• 크기가 양수인 부분 수열 중에서, 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구해라.
• 1부터 N까지 조합의 모든 경우의 수를 구해서 S가 되면 answer++를 해줬다.

정답 풀이

import java.util.*;
import java.io.*;
public class Main {
    static int answer = 0;
    static int S;
    static int[] arr;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());
        arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        for(int size=1;size<=N;size++)
        {
            dfs(0,size,new boolean[N],0,0);
        }
        System.out.println(answer);
    }
    private static void dfs(int sum, int size,boolean[] visited, int depth,int start){
       if(depth==size){
           if(sum==S){
               answer++;
               return;
           }
       }
       for(int i=start;i<arr.length;i++){
           if(!visited[i]){
               visited[i] = true;
               dfs(sum+arr[i],size,visited,depth+1,i+1);
               visited[i] = false;
           }
       }
    }
}
>```

- 풀이를 찾아보니까, 조합 말고 그냥 선택했을 때, 안했을 때를 더 쉽게 나타내는 방법이 있다.
```java
public static void dfs(int index, int sum){
    if(index==N){
        if(sum==target){
            answer++;
        }
        return;
    }
    dfs(index+1,sum+arr[index]); 현재 원소를 선택했을 때
    dfs(index+1,sum);    현재원소를 선택 안했을 때
}

풀이

• 민혁이가 질문하는 세자리 숫자마다 영수가 스트라이크, 볼 개수를 알려준다.
• 이를 통해 영수가 생각하는 답이 가능한 정수의 개수를 구해라.
• 이 문제 어떻게 접근해야할지 갈피를 못 잡았었다. 풀이를 참고했는데, 111999까지의 숫자 배열을 먼저 만들어둔다.(영수가 생각하는 수는 19까지 서로 다른 세개의 숫자로 구성된 세자리 수이므로.)
• 그리고 나서, 민혁이의 추측에 대한 영수의 답을 통해 "절대 될 수 없는 숫자"들을 지워나간다. 예를 들면 429는 1스트라이크 1볼이다 라면, 111~999까지 돌면서 429와 비교해서 1스트라이크 1볼이 안나오는 애들을 다 지우는 것.
• strike+ball 개수만큼 겹치는 수가 있는지 확인한 뒤에, 자리까지 같은 스트라이크 수가 같은지 확인해준다. 다른 부분이 있다면 arr[m]=0 으로 설정.
• arr[m]!=0 인 애들을 센다.이 때, "서로 다른 세자리 수"가 아닌 애들도 다 지운다. 0이 들어가는 애들도 지운다.

정답 풀이

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N =Integer.parseInt(br.readLine());
        StringTokenizer st;
        int[] arr = new int[889];
        int[][] strArr = new int[889][3];
        int answer = 0;
        for(int i=0;i<889;i++){
            arr[i] = 111+i;
            strArr[i][0] = arr[i]/100;
            strArr[i][1] = (arr[i]%100)/10;
            strArr[i][2] = (arr[i]%100)%10;
        }
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            String minhyk = st.nextToken();
            int strike = Integer.parseInt(st.nextToken());
            int ball = Integer.parseInt(st.nextToken());
            int[] temp = new int[3];
            for(int j=0;j<minhyk.length();j++){
                temp[j] = Integer.parseInt(String.valueOf(minhyk.charAt(j)));
            }
            int posCnt = strike+ball;
            for(int m=0;m<strArr.length;m++){
                int[] now = strArr[m];
                int cnt = 0;
                int strikeCnt = 0;
                for(int n=0;n<3;n++){
                    int tempR = temp[n];
                    for(int l=0;l<3;l++){
                        if(tempR==now[l]){
                            cnt++;
                        }
                    }
                }
                if(cnt!=posCnt){
                    arr[m]=0;
                }
                else{
                    for(int l=0;l<3;l++){
                        if(temp[l]==strArr[m][l]){
                            strikeCnt++;
                        }
                    }
                    if(strikeCnt!=strike) arr[m]=0;
                }
            }
        }
        for(int k=0;k<arr.length;k++){
            if(arr[k]!=0 && strArr[k][0]!=strArr[k][1] && strArr[k][1]!=strArr[k][2] &&strArr[k][0]!=strArr[k][2]) {
                if(strArr[k][0]!=0 && strArr[k][1]!=0 && strArr[k][2]!=0) {
                    answer++;
                }
            }
        }
        System.out.println(answer);
    }
}

풀이

• Tn = 1+2+3+...+n = n(n+1)/2 라는 공식이 있고, 정수가 주어졌을 때 정확히 3개의 삼각수의 합으로 표현될 수 있는지를 구해야 한다.
• K의 범위가 3<=K<=1,000 이므로, 1,000까지의 삼각수를 일단 다 구해놓고, 주어지는 k보다 작은 Tn이 어딘지 찾아놨다.(end 변수에 저장)
• 그리고 3중 for문을 찾아놓은 end까지 돌리면서, 세 개의 수 합해서 K가 나오면 true, 아니면 false를 반환하게 구현했다.

정답 풀이

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] tarr = new int[45];
        for(int i=0;i<45;i++){
            tarr[i] = i*(i+1)/2;
        }
        for(int i=0;i<N;i++){
            int num = Integer.parseInt(br.readLine());
            int end = -1;
            for(int k=0;k<tarr.length;k++){
                if(tarr[k]>num){
                    end = k-1;
                    break;
                }
            }
            if(end==-1) end = tarr.length-1;
            boolean find = false;
            L:for(int k=1;k<=end;k++){
                int first = tarr[k];
                for(int m=k;m<=end;m++){
                    int sec = tarr[m];
                    for(int n=m;n<=end;n++){
                        int third = tarr[n];
                        if(first+sec+third==num){
                            System.out.println(1);
                            find = true;   //찾은 경우
                            break L;
                        }
                    }
                }
            }
            if(!find) System.out.println(0);
        }
    }
}
>```

풀이

• N*N 칸의 보드가 주어지고, C,P,Z,Y로 채워져있다.
• 사탕의 색이 다른 인접한 두 칸을 고르고, swap한 뒤 , 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고르고 사탕을 지운다
• 지울 수 있는 사탕의 최대 수를 구해라.
• 완전탐색이니까 진짜 그냥 다 봤다. 2중 for 문 돌리면서 사방탐색으로 자리 바꿔본 뒤,현재 내가 있는 열과 행에서 같은 색으로 이루어져 있는 가장 긴 연속 부분을 찾았다.
• 다 돌고난 뒤, 보드를 처음 상태로 돌려주고 전체 사탕에 대해 반복

정답 풀이

import java.util.*;
import java.io.*;
public class Main {
    static int answer = Integer.MIN_VALUE;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static int N;
    static char[][] map;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new char[N][N];
        for(int i=0;i<N;i++){
            String str = br.readLine();
            for(int j=0;j<N;j++){
                map[i][j] = str.charAt(j);
            }
        }
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                check(i,j);
            }
        }
        if(answer ==Integer.MIN_VALUE) System.out.println(0);
        else System.out.println(answer);
    }
    static void check(int i, int j){
        for(int m=0;m<4;m++){
            int nx = i+dx[m];
            int ny = j+dy[m];
            if(nx>=0 && nx<N && ny>=0 && ny<N){
                char origin = map[i][j];
                char next = map[nx][ny];
                map[i][j] = next;
                map[nx][ny] = origin;
                int rowCnt = 1;
                int colCnt = 1;
                for(int l=0;l<N-1;l++){
                    for(int t=l+1;t<N;t++){
                        if(map[i][l]==map[i][t]){
                            rowCnt++;
                        }
                        else{
                            break;
                        }
                    }
                    for(int t=l+1;t<N;t++){
                        if(map[l][j]==map[t][j]){
                            colCnt++;
                        }
                        else{
                            break;
                        }
                    }
                    answer = Math.max(answer,Math.max(rowCnt,colCnt));
                    rowCnt = 1;
                    colCnt = 1;
                }
                map[i][j] = origin;
                map[nx][ny] = next;
            }
        }
    }
  }
>```

- 4방으로 할 필요 없고, 오른쪽, 아래쪽으로 인접한 애들만 비교해줘도 됨.

풀이

• 어려웠다... 날짜 설정하는 부분을 잘못 생각해서 헤맸음.
• '2022-11-1~2022-11-30'까지 대여 가능하고라는 조건을 충족하기 위해서 'NOT IN END_DATE>'2022-11-01' 로 해주면 되는 것이었다. 대여가 끝나는 날이 2022-11-01 이후라면, 이날부터 빌릴 수가 없으므로.
• 이것 말고는... 딱히 어려운 부분은 없었다. 요금을 구할 때 소수점 단위로 나오는데, 나는 ROUND로 처리했다. 다른 사람들 풀이 보니 FLOOR, TRUNCATE 다 되는 듯.

  🙆‍♀️ 정답 풀이

  WITH CTE AS(
  SELECT C.CAR_ID,C.CAR_TYPE,C.DAILY_FEE,H.START_DATE,H.END_DATE FROM
  CAR_RENTAL_COMPANY_CAR C JOIN CAR_RENTAL_COMPANY_RENTAL_HISTORY H
  ON C.CAR_ID=H.CAR_ID
  WHERE C.CAR_TYPE='세단'or C.CAR_TYPE='SUV')
  

  SELECT DISTINCT C.CAR_ID,P.CAR_TYPE,ROUND((100-discount_rate)/100DAILY_FEE30) AS FEE FROM CAR_RENTAL_COMPANY_DISCOUNT_PLAN P JOIN CTE AS C ON P.CAR_TYPE=C.CAR_TYPE WHERE duration_type regexp ('30일 이상') AND ROUND((100-discount_rate)0.01DAILY_FEE30)>=500000 AND ROUND((100-discount_rate)0.01DAILY_FEE30)<2000000 AND C.CAR_ID NOT IN (SELECT CAR_ID FROM CTE WHERE END_DATE>'2022-11-01') ORDER BY 3 DESC, 2 ASC, 1 DESC;

  ```

풀이

• where 절에 Subquery를 썼다.
• JOIN 필요 없는 간단한 문제. 저번에 배웠던 REGEXP를 활용해봤다.

  🙆‍♀️ 정답 풀이

  SELECT ANIMAL_ID, ANIMAL_TYPE, NAME 
  FROM ANIMAL_INS
  WHERE SEX_UPON_INTAKE REGEXP 'Intact' AND
  ANIMAL_ID IN (SELECT ANIMAL_ID FROM ANIMAL_OUTS WHERE SEX_UPON_OUTCOME REGEXP 'Spayed|Neutered')
  ORDER BY ANIMAL_ID;

풀이

• 리뷰를 가장 많이 작성한 회원의 리뷰를 조회 해야 하기 때문에, 먼저 회원별 리뷰 개수를 나타내는 임시 테이블을 WITH 구문으로 만들어놨다.

• 회원 이름, 리뷰텍스트, 리뷰 작성일이 출력되어야 하므로 MEMBER_PROFILE과 RSET_REVIEW 테이블을 JOIN 하고, WHERE 절에 subquery를 써서, 리뷰개수=MAX(리뷰개수) 인 MEMBER_ID 를 뽑아 일치하는 경우 SELECT 를 하게 했다.

  🙆‍♀️ 정답풀이

  WITH CTE AS(
    SELECT COUNT(*) AS COUNT, MEMBER_ID
    FROM REST_REVIEW R
    GROUP BY MEMBER_ID
  )
  SELECT M.MEMBER_NAME,R.REVIEW_TEXT,DATE_FORMAT(R.REVIEW_DATE,'%Y-%m-%d') AS REVIEW_DATE
  FROM MEMBER_PROFILE AS M JOIN REST_REVIEW R
  ON M.MEMBER_ID=R.MEMBER_ID
  WHERE M.MEMBER_ID IN (SELECT MEMBER_ID
    FROM CTE
    WHERE CTE.COUNT=(SELECT MAX(COUNT) FROM CTE))
  ORDER BY 3,2;

• 음... 게시판 보니까 최다 리뷰 단 회원이 다수인 경우는 고려하지 않은 문제인 것 같다. 내 코드는 최다 리뷰를 단 회원이 다수일 경우도 고려된 코드!🤗