이것저것 개발 블로그

https://www.acmicpc.net/problem/15903

풀이)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main_BJ_15903_카드합체놀이 {
    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());

        PriorityQueue<Long> pq = new PriorityQueue<>();
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++)
            pq.offer(Long.parseLong(st.nextToken()));

        int cnt = 0;
        while(cnt < m){
            long a = pq.poll();
            long b = pq.poll();
            pq.offer(a+b);
            pq.offer(a+b);

            cnt++;
        }

        long sum = 0;
        int size = pq.size();
        for(int i=0; i<size; i++)
            sum += pq.poll();
        System.out.println(sum);

    }//main
}

해당 문제는 그리디로 푸는 문제로, priority queue를 사용하면 쉽게 풀 수 있다!

카드에서 작은 순서대로 정렬을 한 후, 앞에서 2개를 뽑아 더한 수를 다시 pq에 넣어두면, 다시 정렬이 된다.

이 과정을 m번 반복하면 끝!

https://www.acmicpc.net/problem/2217

풀이)

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

public class Main_BJ_2217_로프 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i=0; i<n; i++){
            arr[i] = sc.nextInt();
        }
        Arrays.sort(arr);
        int max = 0;
        for(int i=0; i<n; i++){
            max = Math.max(max, (n-i)*arr[i]);
        }
        System.out.println(max);

    }//main
}

로프의 중량을 받아 정렬을 해준다.

그 후 택한 로프의 최대 중량을 병렬로 연결했을 때의 무게를 계산하면서 max 값을 구하면 된다.

그리디로 해결할 수 있는 간단한 문제!

https://www.acmicpc.net/problem/1932

풀이)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_BJ_1932_정수삼각형 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] tree = new int[n][n];
        int[][] dp = new int[n][n];
        for(int i=0; i<n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<=i; j++){
                tree[i][j] = Integer.parseInt(st.nextToken());
                if(i==n-1){
                   dp[i][j] = tree[i][j];
                }
            }
        }//for

        for(int i=n-2; i>=0; i--){
            for(int j=0; j<=i; j++){
                dp[i][j] = Math.max(dp[i+1][j] + tree[i][j], dp[i+1][j+1]+tree[i][j]);
            }
        }
        System.out.println(dp[0][0]);
    }//main
}

이차원 배열인 tree라는 배열과 dp 배열을 선언한다.

밑에서부터 최대값을 선택하여 더해서 올라가는 방식을 사용했다!

이때, 맨 마지막 줄은 tree와 같은 값을 넣어두고, 더하면서 올라가면 된다.

처음에는 이진 트리처럼 구해서 사용하려 했는데, 아니라는걸 깨닫고 바로 바꿨다..

이후 dp배열의 맨 꼭대기를 출력하면 끝!!

30

23 21

20 13 10

7 12 10 10

4 5 2 6 5

=> 이런 식으로 dp배열이 나오게 된다

https://www.acmicpc.net/problem/1966

풀이)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main_BJ_1966_프린터큐 {
    static class node{
        int loc;
        int w;

        public node(int loc, int w){
            this.loc = loc;
            this.w = w;
        }
    }
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        for(int tc = 0; tc<t; tc++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n =  Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            LinkedList<node> q = new LinkedList<>();

            st = new StringTokenizer(br.readLine());
            for(int i=0; i<n; i++){
                q.offer(new node(i, Integer.parseInt(st.nextToken())));
            }

            int cnt = 0;
            while(!q.isEmpty()){
                node cur = q.poll();
                boolean isMax = true;

                for(int i=0; i<q.size(); i++){
                    if(cur.w < q.get(i).w){
                        q.offer(cur);
                        for(int j=0; j<i; j++)
                            q.offer(q.poll());

                        isMax = false;
                        break;
                    }
                }

                if(!isMax)
                    continue;

                cnt++;
                if(cur.loc == m)
                    break;
            }//while
            System.out.println(cnt);
        }//tc
    }//main
}

큐를 정말 queue로 사용하기보다 linkedlist를 이용해서 구현했다.

이 점을 이용하면 큐 안에 있는 중요도를 볼 수 있어서 편리하다.

현재 중요도보다 큰 애를 발견하면 그 애부터 중요도보다 큰 애 전까지를 큐에 삽입한다.

처음 나온 원소가 가장 큰 경우는 해당 원소의 첫 위치가 m과 같은지를 비교해야 한다.

만약 큐에서 나온 원소보다 중요도가 큰 원소가 있는 경우, 그 원소 앞에 있던 원소들을 뒤로 보내야 한다.

그리고 다시 첫 원소를 빼낸 후 큐에 다시 삽입된 원소보다 중요도가 큰 원소가 있는지 검사해야 한다.

따라서 플래그를 설정해 하는게 편하다!

쉬운 구현 문제인데 고민이 좀 많았다...

https://www.acmicpc.net/problem/1152

풀이)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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());
        System.out.println(st.countTokens());
    }
}

StringTokenizer에서 토큰 수를 셀 수도 있었다.

잠깨우기 위한 간단한 브론즈 문제~

https://www.acmicpc.net/problem/15663

풀이)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main_BJ_15663_N과M9 {
    static HashMap<String, Integer> map = new HashMap<>();
    static int[] ans, arr;
    static boolean[] visited;
    static int n, m;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        arr = new int[n];

        for(int i=0; i<n; i++){
            int num = Integer.parseInt(st.nextToken());
            arr[i] = num;
        }

        ans = new int[m];
        visited = new boolean[n];
        Arrays.sort(arr);
        perm(0);
//        System.out.println(map.keySet());
    }//main
    private static void perm(int cnt){
        if(cnt == m){
            String str = "";
            for(int i=0; i<m; i++)
                str += ans[i] + " ";

            if(!map.containsKey(str)) {
                map.put(str, 1);
                for (int i = 0; i < m; i++) {
                    System.out.print(ans[i] + " ");
                }
                System.out.println();
            }
            return;
        }

        for(int i=0; i<n; i++){
            if(visited[i])
                continue;
            visited[i] = true;
            ans[cnt] = arr[i];
            perm(cnt+1);
            visited[i] = false;
        }
    }//perm
}

반례 찾다가 간단하지만 어이없게 해결한 문제...

일단, 만든 수열이 중복되는지 확인하기 위해 HashMap을 이용해 key로 저장해뒀다.

이때, key는 수열을 string으로 만든것!!

이때 주의할 점이 있다.

띄어쓰기를 꼭 할 것...!

안 했더니 틀렸다...ㅋㅋㅋㅋ

// 반례
4 2
1 11 11 111


//정답
1 11 
1 111 
11 1 
11 11 
11 111 
111 1 
111 11

다른 풀이를 보니 Set을 이용하기도 하고, 이전 값을 저장해서 중복되는지 확인하는 방법도 있었다.

참고하면 좋을듯!!

아, 그리고 ArrayList로 저장해서 contains를 이용하면 시간 초과가 나오니 주의할것!!

https://www.acmicpc.net/problem/9251

풀이)

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main_BJ_9251_LCS {
    static Integer[][] dp;
    static char[] arr1, arr2;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str1 = br.readLine();
        String str2 = br.readLine();
        arr1 = str1.toCharArray();
        arr2 = str2.toCharArray();
        dp = new Integer[arr1.length][arr2.length];

        System.out.println(LCS(arr1.length-1, arr2.length-1));

    }//main
    //TOP DOWN
    private static int LCS(int x, int y){
        if(x < 0 || y < 0)
            return 0;

        //탐색 x
        if(dp[x][y] == null){
            dp[x][y] = 0;

            if(arr1[x] == arr2[y])
                dp[x][y] = LCS(x-1, y-1) + 1;

            else
                dp[x][y] = Math.max(LCS(x-1, y), LCS(x, y-1));
        }
        return dp[x][y];
    }//LCS

    //BOTTOM UP
    /*
    // 공집합 표현을 위해 인덱스가 한 줄씩 추가 됨
		int[][] dp = new int[length_1 + 1][length_2 + 1];

		// 1부터 시작 (index 0 은 공집합이므로 0의 값을 갖고있음)
		for(int i = 1; i <= length_1; i++) {
			for(int j = 1; j <= length_2; j++) {

				// (i-1)과 (j-1) 번째 문자가 서로 같다면
				if(str1[i - 1] == str2[j - 1]) {
					// 대각선 위 (i-1, j-1)의 dp에 +1 한 값으로 갱신
					dp[i][j] = dp[i - 1][j - 1] + 1;
				}

				// 같지 않다면 이전 열(i-1)과 이전 행(j-1)의 값 중 큰 것으로 갱신
				else {
					dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
				}
			}
		}

		// Top-Down 때와는 다르게 dp 인덱스가 한 줄씩 추가되었으므로 -1을 하지 않음
		System.out.println(dp[length_1][length_2]);
     */
}

이 문제는 좀 어려웠다.

각 문자열을 부분집합으로 생각해서 값이 같을때마다 더해가는 방법이 흥미로웠다.

알고리즘 설명대로 하면 Bottom Up 방법이 맞지만, Top Down 방법도 익힐겸 써보았다.

역시나... dp는 어렵다.... 화이팅 해봐야징...ㅠ

이 블로그에서 정말 친절하게 설명해 주셔서 이해를 할 수 있었다. 꼭 다시 풀어봐야지

https://st-lab.tistory.com/139

https://www.acmicpc.net/problem/1629

풀이)

import java.math.BigInteger;
import java.util.Scanner;

public class Main_BJ_1629_곱셈 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        BigInteger a = sc.nextBigInteger();
        BigInteger b = sc.nextBigInteger();
        BigInteger c = sc.nextBigInteger();

        BigInteger ans = a.modPow(b, c);
        System.out.println(ans);
    }
}

BigInteger의 modPow에 대해 배울 수 있는 문제였다.

https://www.acmicpc.net/problem/4153

풀이)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main_BJ_4153_직각삼각형 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] arr = new int[3];

        while(true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int i=0; i<3; i++)
                arr[i] = Integer.parseInt(st.nextToken());

            if(arr[0] == 0 && arr[1] == 0 && arr[2] == 0)
                break;

            Arrays.sort(arr);
            if(arr[0]*arr[0] + arr[1]*arr[1] == arr[2]*arr[2])
                System.out.println("right");
            else System.out.println("wrong");

        }//while
    }//main
}

피타고라스만 알면 간단히 풀 수 있다.

문제에 크기 순으로 준다는 말이 없어서 정렬 했다는 정도!!

아침에 아주 간단히 풀기 좋았음

https://www.acmicpc.net/problem/10866

풀이)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;

public class Main_BJ_10866_덱 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        ArrayDeque<Integer> q = new ArrayDeque<>();
        int n = Integer.parseInt(br.readLine());
        for(int i=0; i<n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            String str = st.nextToken();
            int num = 0;
            if(st.hasMoreTokens())
                num = Integer.parseInt(st.nextToken());

            switch (str){
                case "push_front":
                    q.offerFirst(num);
                    break;
                case "push_back":
                    q.offerLast(num);
                    break;
                case "pop_front":
                    if(q.size() > 0)
                        System.out.println(q.pollFirst());
                    else System.out.println(-1);
                    break;
                case "pop_back":
                    if(q.size() > 0)
                        System.out.println(q.pollLast());
                    else System.out.println(-1);
                    break;
                case "size":
                    System.out.println(q.size());
                    break;
                case "empty":
                    if(q.size() > 0)
                        System.out.println(0);
                    else System.out.println(1);
                    break;
                case "front":
                    if(q.size() > 0)
                        System.out.println(q.peekFirst());
                    else System.out.println(-1);
                    break;
                case "back":
                    if(q.size() > 0)
                        System.out.println(q.peekLast());
                    else System.out.println(-1);
                    break;
            }
        }
    }//main
}

ArrayDeque를 사용하면 금방 풀 수 있는 문제!

사용법을 익히기 좋다.