이것저것 개발 블로그

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

풀이)

import java.util.Scanner;

public class Main_BJ_14916_거스름돈 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        /*
        1   2   3   4   5   6   7   8   9   10
        -1  1  -1   2   1   3   2   4   3   2

        11  12  13  14  15  16  17  18  19  20
        4   3   5   4   3   5   4   6   5   4
         */
        int[] dp = new int[n+1];
        dp[1] = -1;
        for(int i=1; i<=n; i++){
            // 1 3
            if(i/5 == 0 && i%2 == 1)
                dp[i] = -1;
            // 2 4
            else if(i/5 == 0 && i%2 == 0)
                dp[i] = i/2;
            // 5의 배수
            else if(i%5 == 0)
                dp[i] = i/5;
            else{
                //5의 배수가 아니고, 5원 동전 최대 + 나머지 2원으로 거스름돈 가능할 경우
                if(dp[i%5] > 0)
                    dp[i] = i/5 + dp[i%5];
                // 6~9 케이스를 처리하기 위함
                else if(i%2 == 0 && i/5 == 1)
                    dp[i] = i/2;
                // 5원 동전 1개 뺐을 때 + 나머지 2원으로 거스름돈 가능할 경우
                else
                    dp[i] = (i/5-1)+dp[i%5+5];
            }
        }
        System.out.println(dp[n]);
    }//main
}

해당 문제는 dp로 풀어도, 그냥 구현으로 작성해도 괜찮다.

나는 dp아닌 dp로 풀었는데,,,

그냥 케이스 처리 했다고 하는게 더 맞을 듯...

이렇게 안 하고 처음부터 1~5까지는 먼저 선언해버린 후 dp 배열을 계산해도 좋을 것 같다.

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

풀이)

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

public class Main_BJ_2504_괄호의값 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        Stack<Character> stack = new Stack<>();
        int sum = 0;
        int temp = 1;
        for(int i=0; i<str.length(); i++){
            char c = str.charAt(i);
            if(c == '(') {
                stack.push(c);
                temp *= 2;
            }
            else if(c == '['){
                stack.push(c);
                temp *= 3;
            }
            else if(c == ')'){
                if(stack.isEmpty() || stack.peek()!='('){
                    sum = 0;
                    break;
                }
                if(str.charAt(i-1) == '(')
                    sum += temp;

                temp /= 2;
                stack.pop();

            }
            else{
                if(stack.isEmpty() || stack.peek()!='['){
                    sum = 0;
                    break;
                }
                if(str.charAt(i-1) == '[')
                    sum += temp;

                temp /= 3;
                stack.pop();
            }
        }//for
        if(stack.isEmpty())
            System.out.println(sum);
        else System.out.println(0); //stack에 괄호가 존재할경우 짝이 안 맞음
    }//main
}

괄호 짝 맞추기는 했는데 계산하는게 꼬여서 틀렸던 문제다.

먼저, 짝이 맞는 케이스만 생각해보면,,

'('가 들어온다면 temp*=2, '['가 들어온다면 temp*=3을 해준다.

그 후, ')' 이나 ']' 을 만났을 때 전체 값에 temp를 올려서 더해주면 된다.

그리고 ')'이면 /2, ']'이면 /3을 하면 된다.

이때, 주의할 점은 연속된 여는 괄호가 있을 때다. => ([[]]) 와 같은 경우!!

나누기를 계속 해줘야지 중복으로 더하는 것을 방지할 수 있다.

이를 확인하는 방법은 닫힌 괄호가 나올 때마다 그 앞의 괄호와 짝이 맞는지를 확인하면 된다.

짝이 맞는다면 전체 값에 올려주는 과정을 진행하면 되고, 안 맞는다면 나누기만 반복하면 된다.

그리고 예외 케이스로, 짝이 안 맞을 땐 두 가지로 확인할 수 있다.

1. 열린 괄호와 닫힌 괄호가 짝이 안 맞을 때

2. 열린 괄호의 개수가 닫힌 괄호의 개수보다 많아서 짝이 안 맞을 때

1번의 경우 코드에서 닫힌 괄호가 나왔을 때, 스택이 비었거나(짝이 없음) 짝이 안 맞을 경우 바로 전체 값을 0으로 만들어 주었다.

2번의 경우 for문을 다 나와서 stack에 값이 존재하는지를 확인하여 케이스를 처리해주었다.

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

풀이)

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

public class Main_BJ_5014_스타트링크 {
    static int f;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        f = Integer.parseInt(st.nextToken());
        int s = Integer.parseInt(st.nextToken());
        int g = Integer.parseInt(st.nextToken());
        int u = Integer.parseInt(st.nextToken());
        int d = Integer.parseInt(st.nextToken());
        int ans = -1;

        boolean[] building = new boolean[f+1];
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[] {s, 0});
        building[s] = true;
        while(!q.isEmpty()){
            int[] cur = q.poll();
            if(cur[0] == g){
                ans = cur[1];
                break;
            }

            if(check(cur[0]+u) && !building[cur[0]+u]){
                q.add(new int[] {cur[0]+u, cur[1]+1});
                building[cur[0]+u] = true;
            }

            if(check(cur[0]-d) && !building[cur[0]-d]){
                q.add(new int[] {cur[0]-d, cur[1]+1});
                building[cur[0]-d] = true;
            }
        }

        if(ans == -1)
            System.out.println("use the stairs");
        else
            System.out.println(ans);
    }//main
    private static boolean check(int x){
        if(x<=0 || x>f)
            return false;
        return true;
    }
}

이거와 유사한 문제가 많았던 것 같은데, 풀어보길 바란다.

층을 방문했는지 안했는지 boolean 배열을 이용해서 작성하고, bfs를 이용해서 방문 체크를 한다.

이때, u,d를 이용해서 다음 층을 계산하는데, 범위를 넘어가는 것은 큐에 삽입되지 못하도록 check 함수를 만들었다.

그리고 한 칸 씩 넘어갈때마다 방문 횟수를 저장해두면 된다!!

마지막으로, 만약 방문 횟수가 처음에 지정한 -1이라면, 목표 층에 도달하지 못했다는 것이므로 계단을 이용하면 된다.

만약 -1이 아니라면 목표 층에 도달한 것이므로 그 값을 출력하면 끝!

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

풀이)

import java.util.HashMap;
import java.util.Scanner;

public class Main_BJ_1316_그룹단어체커 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int cnt = 0;
        for(int i=0; i<n; i++){
            HashMap<Character, Integer> map = new HashMap<>();
            String str = sc.next();
            char c = str.charAt(0);
            Boolean flag = true;
            for(int j=1; j<str.length(); j++){
                char s = str.charAt(j);
                if(c == s)
                    map.put(s, map.getOrDefault(s, 0)+1);

                else{
                    if(map.containsKey(s)) {
                        flag = false;
                        break;
                    }
                    else map.put(c, 1);

                    c = s;
                }
            }
            if(flag)
                cnt++;
        }
        System.out.print(cnt);
    }//main
}

문자열 크기나 길이나 100밖에 안 되어서 하나하나 확인해도 괜찮다.

연속함을 저장하기 위해 hashmap을 이용했고, 존재하면 map에 넣어줬다.

만약, 앞선 친구와 다른 애가 나올때 map에 존재하는지 체크해주면 된다.

존재한다면, 그룹 단어가 아니라는 의미므로 break 걸어주기!!

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

풀이)

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

public class Main_BJ_1713_후보추천하기 {
    static class Info implements Comparable<Info>{
        int num;
        int cnt;
        int time;
        public Info(int num, int cnt, int time){
            this.num = num;
            this.cnt = cnt;
            this.time = time;
        }
        @Override
        public int compareTo(Info info){
            if(this.cnt==info.cnt)
                return this.time-info.time;
            else if(this.cnt<info.cnt)
                return -1;
            else return 1;
        }
    }//info

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int p = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        LinkedList<Info> list = new LinkedList<>();
        for(int i=0; i<p; i++){
            int student = Integer.parseInt(st.nextToken());
            if(list.size() < n){
                boolean flag = false;
                for(int j=0; j<list.size(); j++){
                    if(list.get(j).num == student){
                        list.get(j).cnt++;
                        flag = true;
                        break;
                    }
                }
                if(!flag)
                    list.add(new Info(student, 1, i));
            }
            else {
                Collections.sort(list);
                boolean flag = false;
                for (int j = 0; j < list.size(); j++) {
                    //있을 때
                    if (list.get(j).num == student) {
                        list.get(j).cnt++;
                        flag = true;
                        break;
                    }
                }
                if(!flag){
                    list.remove(0);
                    list.add(new Info(student, 1, i));
                }
            }
        }

        int[] pic = new int[n];
        for(int i=0; i<list.size(); i++){
            pic[i] = list.get(i).num;
        }
        Arrays.sort(pic);
        for(int i=0 ;i<n; i++){
            if(pic[i] != 0)
                System.out.print(pic[i]+" ");
        }

    }//main
}

시간을 계산하기가.... 좀 까다로웠다..

처음에는 일일히 셌는데, 그럴필요 없이 class 하나 정해두고 만들면 된다.

또한, 시간 부분은 그냥 추천 그림 개수에 맞춰서 for문을 돌 때, Index로 저장해두면,

index가 작은 친구가 자동으로 오래 저장된 친구라 그렇게 하면 된다.

처음에 아주 간단하다고 생각하고 풀었는데,,,, 생각보다 많이 틀려서 당황한 문제...

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

풀이)

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

public class Main_BJ_7562_나이트의이동 {
    static int[] dx = {-1, -2, -2, -1, 1, 2, 2, 1};
    static int[] dy = {-2, -1, 1, 2, 2, 1, -1, -2};
    static int[][] map;
    static boolean[][] visited;
    static int l, endx, endy;
    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++){
            l = Integer.parseInt(br.readLine());
            map = new int[l][l];
            visited = new boolean[l][l];

            StringTokenizer st = new StringTokenizer(br.readLine());
            int curx = Integer.parseInt(st.nextToken());
            int cury = Integer.parseInt(st.nextToken());
            map[curx][cury] = 1;

            st = new StringTokenizer(br.readLine());
            endx = Integer.parseInt(st.nextToken());
            endy = Integer.parseInt(st.nextToken());

            int cnt = bfs(curx, cury);
            System.out.println(cnt);
        }//test case
    }//main
    private static int bfs(int x, int y){
        Queue<int[]> q = new ArrayDeque<>();
        visited[x][y] = true;
        q.add(new int[] {x, y, 0});

        while (!q.isEmpty()){
            int[] cur = q.poll();
            if(cur[0] == endx && cur[1] == endy)
                return cur[2];

            for(int i=0; i<8; i++){
                int nx = cur[0]+dx[i];
                int ny = cur[1]+dy[i];

                if(check(nx, ny) && !visited[nx][ny]){
                    q.add(new int[] {nx, ny, cur[2]+1});
                    visited[nx][ny] = true;
                }
            }
        }//while

        return -1;
    }//bfs
    private static boolean check(int x, int y){
        if(x<0 || y<0 || x>=l || y>=l)
            return false;
        return true;
    }
}

BFS를 이용하면 쉽게 풀 수 있다!

이때, 나이트 위치 이동만 신경써서 dx, dy를 작성해주고, bfs코드에서도 queue 이동할 때 이동 숫자만 잘 체크해주면 된다.

그러면 간단하게 끝!

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

풀이)

<틀린답>

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

public class Main_BJ_1912_연속합 {
    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];
        int[] sum = new int[n+1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        int s = arr[0];
        for(int i=1; i<=n; i++){
            if(i==1)
                sum[i] = s;
            else{
                sum[i] = s+arr[i-1];
                s += arr[i-1];
            }
        }

        int ans = Integer.MIN_VALUE;
        for(int i=0; i<n; i++){
            for(int j=i+1; j<=n; j++){
                ans = Math.max(ans, sum[j]-sum[i]);
            }
        }
        System.out.println(ans);
    }//main
}

처음에는 누적합으로 풀면 되겠다~ 했는데 시간초과 났다.

당연히 10만 * 10만 = 100억...이라서 100초 걸리는 거였음....

<정답>

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

public class Main_BJ_1912_연속합 {
    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];
        int[] sum = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        sum[0] = arr[0];
        int ans = arr[0];
        for(int i=1; i<n; i++){
            sum[i] = Math.max(sum[i-1]+arr[i], arr[i]);
            ans = Math.max(ans, sum[i]);
        }

        System.out.println(ans);
    }//main
}

연속되면서 가장 큰 합을 찾으면 되기 때문에 dp 배열을 하나 만든다.

그후 차례로 "이전까지의 최대값 + 현재값"과 현재 값을 비교한다.

만약 현재값이 더 크면 현재값에서부터 누적해서 더 큰 값을 찾는다고 생각하면 쉽다!

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

풀이)

import java.util.Scanner;

public class Main_BJ_15651_N과M3 {
    static int n, m;
    static int[] pick;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        pick = new int[m];
        perm(0);
        System.out.println(sb);
    }
    private static void perm(int cnt){
        if(cnt == m){
            for(int i=0; i<m; i++){
                sb.append(pick[i]).append(" ");
            }
            sb.append("\n");
            return;
        }
        for(int i=0; i<n; i++){
            pick[cnt] = i+1;
            perm(cnt+1);
        }

    }//perm
}

중복순열을 뽑아내는 문제였다!

이때, Stringbuilder를 사용하지 않고, 그냥 출력하면 시간 초과가 나니까 주의하기!

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

풀이)

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

public class Main_BJ_11729_하노이탑이동순서 {
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        sb.append((int)(Math.pow(2,n)-1)+"\n");
        moving(n, 1, 2, 3);
        System.out.println(sb);
    }//main
    private static void moving(int n, int start, int mid, int to){
        if(n == 1){
            sb.append(start+" "+to+"\n");
            return;
        }

        moving(n-1, start, to, mid);
        sb.append(start+" "+to+"\n");
        moving(n-1, mid, start, to);
    }//moving
}

재귀를 안다면 나름 간단하게 풀 수 있다.

대신, 하노이의 탑 규칙을 알아야 한다!

그리고, 시간 초과가 나올 수 있으므로 stringbuilder 사용해주면 간편!

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

풀이)

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

public class Main_BJ_14889_스타트와링크 {
    static int[][] map;
    static int n, ans = Integer.MAX_VALUE;
    static boolean[] visited;
    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];
        visited = new boolean[n];
        for(int i=0; i<n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<n; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        comb(0, 0);
        System.out.println(ans);

    }//main
    private static void comb(int idx, int cnt){
        if(cnt == n/2){
            cal();
            return;
        }

        for(int i=idx; i<n; i++){
            if(visited[i])
                continue;

            visited[i] = true;
            comb(i+1, cnt+1);
            visited[i] = false;
        }

    }//comb
    private static void cal(){
        int start=0;
        int link=0;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(visited[i] && visited[j])
                    start += map[i][j]+map[j][i];
                else if(!visited[i] && !visited[j])
                    link += map[i][j]+map[j][i];
            }
        }
        start /= 2;
        link /= 2;
        ans = Math.min(ans, Math.abs(start-link));
    }
}

조합으로 경우의 수를 구하고, start와 link에 해당하는 점수를 구해주면 된다.

이때, for문으로 돌릴 경우 이중으로 더해진다는 점을 참고하기!!!

(아니면 for문 내에서 자체적으로 두 번 안 더하게끔 하면 된다. 그걸 이제 보고 생각남..ㅎ)

처음에는 무조건 4팀중 반반으로 나눠야 하는줄 알고,,,,,,, 실버2맞나...? 생각보다 더 높아야 하는거 아닌가...? 했는데

그게 아니었고 그냥 내가 잘못 본거였다...ㅠ

문제 똑바로 잘 읽기...ㅎ