[BOJ] 16235. 나무 재테크 - Simultaion

제출일 : 2019-10-15

문제 풀이 시간 : 2H

난이도 : ★★★☆

Problem

link : https://www.acmicpc.net/problem/16235

Input

첫째 줄에 K년이 지난 후 살아남은 나무의 수를 출력한다.

Output

인구 이동이 몇 번 발생하는지 첫째 줄에 출력한다.

Constraint

• 1 ≤ N ≤ 10
• 1 ≤ M ≤ N2
• 1 ≤ K ≤ 1,000
• 1 ≤ A[r][c] ≤ 100
• 1 ≤ 입력으로 주어지는 나무의 나이 ≤ 10
• 입력으로 주어지는 나무의 위치는 모두 서로 다름

Example

input

5 2 4
2 3 2 3 2
2 3 2 3 2
2 3 2 3 2
2 3 2 3 2
2 3 2 3 2
2 1 3
3 2 3

output

13

Solution & Inpression

시뮬레이션 문제

문제에서 시키는데로 차근차근 풀게되면 어려움이 없는 문제지만

1*1 한칸에 여러 나무가 심어질수 있기때문에 자료구조를 어떻게 해야할지 고민을 하게 만든 문제였다.

처음 내가 생각한 자료구조는 ArrayList<Integer>[][]로 2차원 배열의 원소값이 ArrayList로 이루어진 자료구조를 선언하고 사용하려 했다.

하지만 다른 2차원 배열과 다르게 사용을 할 수 가 없었고, 모든 나무를 하나의 PriorityQueue에 모든 정보를 담아 문제를 풀었다.

Code

언어 : JAVA

메모리 : 165,300 kb

실행시간 : 1,532 ms

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

class Main {
    static int N, M, K;
    static int[][] robot, land;

    static PriorityQueue<Tree> tree;

    static int[] dr = { -1, -1, -1, 0, 0, 1, 1, 1 };
    static int[] dc = { -1, 0, 1, -1, 1, -1, 0, 1 };

    static class Tree implements Comparable<Tree> {
        int r, c, age;

        public Tree(int r, int c, int age) {
            this.r = r;
            this.c = c;
            this.age = age;
        }

        public int compareTo(Tree t) {
            return this.age > t.age ? 1 : -1;
        }

        public String toString() {
            return "(r=" + r + ", c=" + c + ", age=" + age + ")";
        }

    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt() + 1; // 땅의 크기 1base
        int M = sc.nextInt(); // 나무 수
        int K = sc.nextInt(); // 년 수
        robot = new int[N][N];
        land = new int[N][N];

        for (int i = 1; i < N; i++) {
            for (int j = 1; j < N; j++) {
                robot[i][j] = sc.nextInt();// 로봇이 추가하는 양분
                land[i][j] = 5; // 초기 양분
            }
        }

        tree = new PriorityQueue<>();
        for (int i = 0; i < M; i++) {
            tree.offer(new Tree(sc.nextInt(), sc.nextInt(), sc.nextInt()));
        }
        ArrayList<Tree> dead = new ArrayList<>();
        ArrayList<Tree> alive = new ArrayList<>();
        for (int year = 0; year < K; year++) {
            // 봄
            while (!tree.isEmpty()) {
                Tree t = tree.poll();
                if (land[t.r][t.c] < t.age) {// 죽는다
                    dead.add(t);
                } else {
                    land[t.r][t.c] -= t.age; // 양분을 먹고
                    t.age++; // 한살도 먹고
                    alive.add(t);
                }
            }

            // 여름
            for (int i = 0; i < dead.size(); i++) {
                Tree t = dead.get(i);
                // 나이를 2로 나눈 값이 나무가 있던 칸에 양분으로 추가된다
                land[t.r][t.c] += t.age / 2;
            }
            dead.clear();

            // 가을
            for (int i = 0; i < alive.size(); i++) {
                Tree t = alive.get(i);
                if (t.age % 5 != 0) {// 번식하지 못하는 나무
                    tree.offer(t);
                } else {
                    tree.offer(t);
                    for (int k = 0; k < 8; k++) {
                        int r = t.r + dr[k];
                        int c = t.c + dc[k];
                        if (1 <= r && r < N && 1 <= c && c < N) {
                            Tree nt = new Tree(r, c, 1);
                            //System.out.println("    " + nt);
                            tree.offer(nt);
                        }
                    }
                }
            }
            alive.clear();

            // 겨울
            for (int i = 1; i < N; i++) {
                for (int j = 1; j < N; j++) {
                    land[i][j] += robot[i][j];
                }
            }
        }
        System.out.println(tree.size());

    }
}

Disjoint-Set (서로소 집합)

서로 중복되지 않는 부분 집합들 로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조

• 즉, 공통 원소가 없는 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 자료구조이다.

Union-Find

Disjoint Set을 표현할 때 사용하는 알고리즘

Union-Find의 연산

• make-set(x)

  • 초기화
  • x를 유일한 원소로 하는 새로운 집합을 만든다.

  private static void makeSet(int n){
      parent = new int[n];
      for(int i = 1; i <= n; i++){
      parent[i] = i;
  }

• union(x, y)

  • 합하기
  • x가 속한 집합과 y가 속한 집합을 합친다. 즉, x와 y가 속한 두 집합을 합치는 연산

  private static void union(int x, int y) {
      x = find(x);
      y = find(y);
      if (x != y) {
          if (x < y)
              parent[y] = x;
          else
              parent[x] = y;
      }
  }

• find(x)

  • 찾기
  • x가 속한 집합의 대표값(루트 노드 값)을 반환한다. 즉, x가 어떤 집합에 속해 있는지 찾는 연산

  private static int find(int x) {
      if (x == parent[x])
          return x;
      else
          return parent[x] = find(parent[x]);
  }

[BOJ] 14891. 톱니바퀴 - Simulation

제출일 : 2019-10-14

문제 풀이 시간 : 1H

난이도 : ★★★

Problem

link : https://www.acmicpc.net/problem/14891

Input

첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 시계방향 순서대로 주어진다. N극은 0, S극은 1로 나타나있다.

다섯째 줄에는 회전 횟수 K(1 ≤ K ≤ 100)가 주어진다. 다음 K개 줄에는 회전시킨 방법이 순서대로 주어진다. 각 방법은 두 개의 정수로 이루어져 있고, 첫 번째 정수는 회전시킨 톱니바퀴의 번호, 두 번째 정수는 방향이다. 방향이 1인 경우는 시계 방향이고, -1인 경우는 반시계 방향이다.

Output

총 K번 회전시킨 이후에 네 톱니바퀴의 점수의 합을 출력한다. 점수란 다음과 같이 계산한다.

• 1번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 1점
• 2번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 2점
• 3번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 4점
• 4번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 8점

Example

input

10101111
01111101
11001110
00000010
2
3 -1
1 1

output

7

Solution & Inpression

Code

언어 : JAVA

메모리 : 14,536 kb

실행시간 : 124 ms

import java.util.*;

public class Main {
    static int[][] wheels;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        wheels = new int[5][8];
        for (int i = 1; i <= 4; i++) {
            String str = sc.next();
            for (int j = 0; j < 8; j++) {
                if (str.charAt(j) == '1')
                    wheels[i][j] = 1; // S극
                else
                    wheels[i][j] = 0; // N극
            }
        }

        int K = sc.nextInt(); // 회전 횟수 K;
        for (int i = 0; i < K; i++) {
            // 톱니바퀴 번호, 방향(1:시계 -1:반시계)
            isspin(sc.nextInt(), sc.nextInt());
        }

        System.out.println(1 * wheels[1][0] 
                         + 2 * wheels[2][0] 
                         + 4 * wheels[3][0] 
                         + 8 * wheels[4][0]);

        sc.close();
    }

    //좌우에 톱니를 회전할 수 있는지 확인.
    private static void isspin(int num, int dir) { 
        //회전이 가능한 톱니번호와 뱡향을 저장
        ArrayList<int[]> list = new ArrayList<>(); 

        list.add(new int[] { num, dir });

        int flag = dir;
        int temp = num;
        int right = wheels[num][2]; //현재 바퀴의 오른쪽값.
        while (temp + 1 <=4) { // 오른쪽에 바퀴가 존재한다면
            if (right != wheels[temp + 1][6]) {//회전이 가능한지 
                temp++;
                flag *= -1;
                right = wheels[temp][2]; 
                list.add(new int[] { temp, flag });
            }
            else
                break;
        }

        flag = dir;
        temp = num;
        int left = wheels[num][6]; //현재 바퀴의 왼쪽값.
        while (temp - 1 >=1) { // 왼쪽에 바퀴가 존재한다면
            if (left != wheels[temp - 1][2]) { //회전이 가능한지
                temp--;
                flag *= -1; //반대방향
                left = wheels[temp][6]; 
                list.add(new int[] { temp, flag });
            }
            else
                break;
        }
        for (int i = 0; i < list.size(); i++) {
            spin(list.get(i)[0], list.get(i)[1]);
        }
    }

    private static void spin(int num, int dir) {
        int[] temp = wheels[num].clone(); // 복사

        if (dir == 1) {// 시계방향이면 >> 오른쪽으로 한칸씩
            for (int i = 1; i < 8; i++) {
                wheels[num][i] = temp[i - 1];
            }
            wheels[num][0] = temp[7];
        } else {// 반시계방향이면 >> 왼쪽으로 한칸씩
            for (int i = 1; i < 8; i++) {
                wheels[num][i - 1] = temp[i];
            }
            wheels[num][7] = temp[0];
        }
    }
}

[BOJ] 14890. 경사로 - Simulation

제출일 : 2019-10-14

문제 풀이 시간 : 2H

난이도 : ★★★★☆

Problem

link : https://www.acmicpc.net/problem/14890

Input

첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다.

Output

첫째 줄에 지나갈 수 있는 길의 개수를 출력한다.

Example

input

6 2
3 3 3 3 3 3
2 3 3 3 3 3
2 2 2 3 2 3
1 1 1 2 2 2
1 1 1 3 3 1
1 1 2 3 3 2

output

3

Solution & Inpression

해결하지 못한 문제.

Code

언어 : JAVA

메모리 : 25,868 kb

실행시간 : 240 ms

import java.util.*;

public class Main {
    static int[][] wheels;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        wheels = new int[5][8];
        for (int import java.util.ArrayList;
import java.util.Scanner;

public class Main {

    static int N, L;
    static int[][] map;
    static boolean[][] visitRow, visitCol;

    static ArrayList<int[]> v;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        L = sc.nextInt();

        map = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                map[i][j] = sc.nextInt();
            }
        }    
        int ans = 0;
        int j = 0;// 끝에 도착시 j로 체크
        for (int i = 0; i < N; i++) {
            int cnt = 1;
            for (j = 0; j < N-1; j++) { //가로: 좌->우
                     if(map[i][j]  ==map[i][j+1])            cnt++; //평지
                else if(map[i][j]+1==map[i][j+1] && cnt>= L) cnt=1; //오르막
                else if(map[i][j]-1==map[i][j+1] && cnt>= 0) cnt=-L+1; //내리막
                else break;
            }
            if(j==N-1 && cnt>= 0) ans++; //끝에 도착

            cnt=1;
            for (j = 0; j < N-1; j++) { //세로: 상->하
                     if(map[j][i]  ==map[j+1][i])            cnt++; //평지
                else if(map[j][i]+1==map[j+1][i] && cnt>= L) cnt=1; //오르막
                else if(map[j][i]-1==map[j+1][i] && cnt>= 0) cnt=-L+1; //내리막
                else break;
            }
            if(j==N-1 && cnt>= 0) ans++; //끝에 도착

        }

        System.out.println(ans);
    }
}

[BOJ] 14889. 스타트와 링크- Permutation

제출일 : 2019-10-14

문제 풀이 시간 : 40M

난이도 : ★★

Problem

link : https://www.acmicpc.net/problem/148989

Input

첫째 줄에 N(4 ≤ N ≤ 20, N은 짝수)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.

Output

첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.

Example

input

4
0 1 2 3
4 0 5 6
7 1 0 2
3 4 5 0

output

0

Solution & Inpression

N개중 N/2개를 선택하여 2개의 그룹으로 나눈뒤 각각의 그래프의 가중치를 더해 최솟값을 찾는 문제. [BOJ]게리멘더링을 풀기전에 풀어보았더라면 게리멘더링을 더 쉽게 풀었을것 같다.

Code

언어 : JAVA

메모리 : 17,560kb

실행시간 : 336 ms

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int[][] matrix;
    static int[] visit;
    static int min;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        matrix = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                matrix[i][j] = sc.nextInt();
            }
        }
        min = Integer.MAX_VALUE;
        visit = new int[N];
        solve(N, N / 2, 0, 0);
        System.out.println(min);

    }

    static void solve(int n, int r, int depth, int start) {
        if(depth!=0&&visit[0]==0)
            return;
        if (depth == r) {
            int team1 = 0, team2 = 0;
            //System.out.println(Arrays.toString(visit));
            for (int i = 0; i < n; i++) {
                if (visit[i] == 1)
                    for (int j = 0; j < n; j++) {
                        if (i != j && visit[j] == 1)
                            team1 += matrix[i][j];
                    }
                else
                    for (int j = 0; j < n; j++) {
                        if (i != j && visit[j] == 0)
                            team2 += matrix[i][j];
                    }
            }
            int res = Math.abs(team1 - team2);
            if (res < min)
                min = res;
            return;
        }

        for (int i = start; i < n; i++) {
            if (visit[i] == 0) {
                visit[i] = 1;
                solve(n, r, depth + 1, i);
                visit[i] = 0;
            }
        }
    }
}

[BOJ] 14888. 연산자끼워넣기 - Permutation

제출일 : 2019-10-14

문제 풀이 시간 : 1H

난이도 : ★★☆

Problem

link : https://www.acmicpc.net/problem/148989

Input

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다.

Output

첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력한다. 최댓값과 최솟값이 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.

Example

input

4
0 1 2 3
4 0 5 6
7 1 0 2
3 4 5 0

output

0

Solution & Inpression

최대 10!의 경우의 수가 나오기때문에 완전탐색으로 풀어도 가능한 문제로 순열을 이용하여 해결하였다. 입력이 N개의 숫자에 대해 N-1개의 사칙연산의 개수가 주어지는데 이를 N-1크기의 배열로 값을 받았다.

Code

언어 : JAVA

메모리 : 15,140kb

실행시간 : 352 ms

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static boolean[] visit;
    static int[] numbers;
    static int[] op;
    static int n, max, min;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        numbers = new int[n];

        for (int i = 0; i < n; i++)
            numbers[i] = sc.nextInt();

        op = new int[n - 1];
        int idx = 0;
        for (int i = 0; i < 4; i++)
            for (int j = sc.nextInt(); j > 0; j--)
                op[idx++] = i + 1;

        max = Integer.MIN_VALUE;    min = Integer.MAX_VALUE;
        visit = new boolean[n - 1];

        solve(0, 1, numbers[0], 0);
        System.out.println(max);    System.out.println(min);

    }

    public static void solve(int v, int idx, int num, int len) {
        int result = 0;
        if (len == n - 1) {
            if (num > max)    max = num;
            if (num < min)    min = num;
            return;
        }

        for (int i = 0; i < n - 1; i++) {
            if (!visit[i]) {
                visit[i] = true;
                switch (op[i]) {
                case 1:    result = num + numbers[idx];    break;
                case 2:    result = num - numbers[idx];    break;
                case 3:    result = num * numbers[idx];    break;
                case 4:    result = num / numbers[idx];    break;
                }
                solve(i, idx + 1, result, len + 1);
                visit[i] = false;
            }
        }
    }
}

CaseOfNumber - 조합 & 중복조합 &순열 & 중복순열

조합(Combination)

서로 다른 물건들 중 몇 가지 대상을 뽑는 것을 조합이라고 한다.

서로 다른 n 개의 원소 중 r 개를 선택 (순서 X, 중복 X)

중복 조합(Homogeneous)

서로 다른 종류의 대상들 중에서 중복을 허락하여 몇 개를 택하는 조합을 중복조합이라고 한다.

서로 다른 n 개의 원소 중 r 개를 선택 (순서 X, 중복 O)

순열(Permutation)

서로 다른 물건들 중 몇 가지 대상을 뽑아 일렬로 나열하는 것을 순열이라고 한다.

서로 다른 n개의 원소 중 r개를 선택 (순서O , 중복 O)

중복 순열(Product)

서로 다른 물건들 중에서 중복을 허용하여 몇 개를 택하는 순열을 중복순열이라고 한다.

서로 다른 n개의 원소 중 r개를 선택 (순서O , 중복 O)

code

import java.util.Arrays;

public class MyCombi {
    static int[] data = { 1,2,3,4 };
    static int[] res;
    static boolean[] visit;
    static int cnt;

    public static void main(String[] args) {
        int N = 4, R = 2;
        res = new int[R];
        visit = new boolean[N];

        cnt = 0;
        solve1(N, R, 0);
        System.out.println(cnt);

        cnt = 0;
        solve2(N, R, 0);
        System.out.println(cnt);

        cnt = 0;
        solve3(N, R, 0, 0);
        System.out.println(cnt);

        cnt = 0;
        solve4(N, R, 0, 0);
        System.out.println(cnt);
    }

    //중복순열: 순서가 중요하고(123!=321), 중복을 허용하는 경우
    private static void solve1(int n, int r, int depth) {
        if (depth == r) {
            System.out.println(Arrays.toString(res));
            cnt++;
            return;
        }

        for (int i = 0; i < n; i++) {
            res[depth] = data[i];
            solve1(n, r, depth + 1);
        }
    }

    //순열: 순서가 중요하고(123!=321), 중복을 허용하지 않는 경우
    private static void solve2(int n, int r, int depth) {
        if (depth == r) {
            System.out.println(Arrays.toString(res));
            cnt++;
            return;
        }

        for (int i = 0; i < n; i++) {
            if (visit[i] == false) {
                visit[i] = true;
                res[depth] = data[i];
                solve2(n, r, depth + 1);
                visit[i] = false;
            }
        }
    }

    //중복조합: 순서가 중요하지 않고(123==321), 중복을 허용하는 경우
    private static void solve3(int n, int r, int depth, int start) {
        if (depth == r) {
            System.out.println(Arrays.toString(res));
            cnt++;
            return;
        }

        for (int i = start; i < n; i++) {
            res[depth] = data[i];
            solve3(n, r, depth + 1, i);
        }
    }

    //조합: 순서가 중요하지 않고(123==321), 중복을 허용하지 않는 경우
    private static void solve4(int n, int r, int depth, int start) {
        if (depth == r) {
            System.out.println(Arrays.toString(res));
            cnt++;
            return;
        }

        for (int i = start; i < n; i++) {
            if (visit[i] == false) {
                visit[i] = true;
                res[depth] = data[i];
                solve4(n, r, depth + 1, i);
                visit[i] = false;
            }
        }
    }

}

[SWEA] 7701. 염라대왕의 이름 정렬 D4 - TreeSet

제출일 : 2019-10-08

문제 풀이 시간 : 15M

난이도 : ★☆

Problem

link : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWqU0zh6rssDFARG

Input

첫 번째 줄에 테스트 케이스의 수 T(1 ≤ T ≤ 50)가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 이승 명부의 이름 개수 N(1 ≤ N ≤ 20,000)이 주어진다.

각 테스트 케이스의 두 번째 줄부터 N개의 줄에 걸쳐서 알파벳 소문자로 이루어진 이름들이 주어진다.

이름에는 공백이 포함되지 않으며 최소 1개, 최대 50개의 알파벳으로 이루어져 있다.

Output

각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고,

정리된 이름을 한 줄에 하나씩 출력하라. 같은 이름은 한 번만 출력해야 하는 것을 주의하라.

Example

input

2
5
my
name
is
ho
seok
12
s
a
m
s
u
n
g
j
j
a
n
g

output

#1
ho
is
my
name
seok
#2
a
g
j
m
n
s
u

Solution & Inpression

문제를 잘 읽고 문제에 맞추어 구현하면 되는 문제

Set, TreeSet, Comparator, comparTo등 자료구조와 함수를 알고 있다면 쉽게 해결할 수 있는 문제.

Code

언어 : JAVA

메모리 : 102,728 kb

실행시간 : 4,681 ms

import java.io.*;
import java.util.*;
public class Solution {
    public static void main(String[] args) throws Exception {
        System.setIn(new FileInputStream("res/D4_7701_염라대왕의이름정렬.txt"));
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        for (int tc = 1; tc <= T; tc++) {
            int N = sc.nextInt();

            Set<String> set = new TreeSet<>(new Comparator<String>() { 
                @Override
                public int compare(String o1, String o2) {
                    int r = o1.length() - o2.length();
                    if (r == 0)
                        return o1.compareTo(o2);
                    else
                        return r;
                }
            });

            for (int i = 0; i < N; i++) {
                set.add(sc.next());
            }

            System.out.println("#"+tc);

            for (String string : set) {
                System.out.println(string);
            }


        }
    }
}