알고리즘 재활 2일차 - 백준 2751, 10814, 11726, 1074번

너 뭐여.. 너 무슨 유형이야

 

 

수 정렬하기 2

 

 

간단하게 sort 메서드로 정렬

 

import java.io.*;
import java.util.*;
 
public class Main { // S5 수 정렬하기 2
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
 
        int N = Integer.parseInt(st.nextToken());
        int [] arr = new int[N];
 
        for(int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
 
        Arrays.sort(arr);
        for(int s : arr){
            sb.append(s);
            sb.append("\n");
        }
 
        System.out.println(sb);
    }
}
 

---

나이순 정렬

 

 

정렬 중에서도 요소가 2개 이상일 때 @Override 해서 원하는 조건으로 sorting 해주면 된다.

public static class Member {
        int age;
        String name;

        public Member(int age, String name) {
            this.age = age;
            this.name = name;
        }
    }

 

Member로 클래스를 하나 만들어서 age와 name을 관리했고,

        // 나이 순
        Arrays.sort(member, new Comparator<Member>() {
            @Override
            public int compare(Member s1, Member s2) {
                return s1.age - s2.age;
            }
        });

 

compare 메서드를 재정의해서 age로 정렬해 주었다.

 

import java.io.*;
import java.lang.reflect.Member;
import java.util.*;
 
public class Main { // S5 10814 나이 순 정렬
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
 
        int N = Integer.parseInt(st.nextToken());
        Member[] member = new Member[N];
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int age = Integer.parseInt(st.nextToken());
            String name = st.nextToken();
            member[i] = new Member(age, name);
        }
 
        // 나이 순
        Arrays.sort(member, new Comparator<Member>() {
            @Override
            public int compare(Member s1, Member s2) {
                return s1.age - s2.age;
            }
 
        });
 
        for(Member m : member){
            sb.append(m.age).append(" ");
            sb.append(m.name).append("\n");
        }
        System.out.println(sb);
    }
 
    public static class Member {
        int age;
        String name;
 
        public Member(int age, String name) {
            this.age = age;
            this.name = name;
        }
    }
}
 

 

 

---

2×n 타일링

 

DP는 언제나 손으로 ㅎㅎ

 

규칙을 찾다 보니 홀/짝수일 때 규칙이 존재했다.

dp [i-1]에서 1개의 블록을 붙이고, dp [i-2]에서 붙여주면 현재의 블록 조합을 알 수 있었다.

사실 N = 9일 때 55인 거 보고 피보나치가 떠올랐다.

점화식 간단하게 세워주고 풀었다.

Dp[i] = Dp[i-1] + Dp[i-2]

 

import java.io.*;
import java.util.*;
 
public class Main { // S3 2xn 타일링
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int N = Integer.parseInt(st.nextToken());
        int[] dp = new int[Math.max(N + 1, 2)];
 
        dp[0] = 1;
        dp[1] = 1;
 
        for (int i = 2; i <= N; i++) {
            // 아오 괄호 ㅋ ㅋ ㅋ ㅋㅋㅋㅋㅋㅋㅋ
            dp[i] = (dp[i - 1] + dp[i - 2]) % 10007;
        }
 
        System.out.println(dp[N]);
    }
}

---

Z

 

Zzzz ZZzzz..

 

 

규칙을 찾아 분할해서 풀어야 하는 문제다.

사실 어떻게 푸는지도 알았는데 이게 오랜만이고 실수를 너무 많이 해서 꼬였다.. 꼴꼴

 

먼저 size를 확인하고 범위를 쪼갤 때마다 size를 2로 나눠주어야 한다.

범위를 4 범위로 나누고 해당 범위에 내가 찾으려는 r과 c가 있다면 그 r과 c까지 분할해서 정복하면 된다.

탐색 중 r과 c가 범위에서는 해당 범위의 제곱을 더해준다 (어차피 지나갈 길이니까)

 

위 예시로는 r = 3, c = 1에 11이 존재한다.
칸을 size/2 를 통해 4칸으로 쪼개주고, r과 c가 있는 곳을 탐색해 준다.
2 사분면과 1 사분면에는 없으므로 이에 해당하는 범위 값, 제곱 *2  (size^2)를 answer에 더해준다

3 사분면에 존재하므로, 해당 범위에서 재귀함수를 호출하여 1칸일 때까지 탐색한다.

 

 

import java.io.*;
import java.util.*;
 
public class Main { // S1 Z
    static int r, c, answer = 0;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int N = Integer.parseInt(st.nextToken());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        answer = 0;
        int size = (int) Math.pow(2, N);
        dfs(size, 0, 0);
        System.out.println(answer);
 }
 
    public static void dfs(int size, int now_r, int now_c) {
        if (size == 1) {
            return;
        }
 
        int next_size = size/2 ;
 
        // 2사분면 -> 1사분면 -> 3사분면 -> 4사분면
        // 만약 4사분면에 있다면 1,2,3 분면은 스킵. 따라서 size^2 * 3 더해줌
        if (r < now_r + next_size && c < now_c + next_size) {
            dfs(next_size, now_r, now_c);
        } else if (r < now_r + next_size && c >= now_c + next_size) {
            answer += next_size * next_size;
            dfs(next_size, now_r, now_c + next_size);
        } else if (r >= now_r + next_size && c < now_c + next_size) {
            answer += 2 * next_size * next_size;
            dfs(next_size, now_r + next_size, now_c);
        } else {
            answer += 3 * next_size * next_size;
            dfs(next_size, now_r + next_size, now_c + next_size);
        }
    }
}