문제 링크

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

접근 방법

최단 시간에 도착해야 하기 때문에 bfs

나이트가 갈 수 있는 방향을 8방으로 지정해두고 이동 횟수를 추가하여 진행

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

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokens;

        int T = Integer.parseInt(br.readLine());

        while (T-- > 0) {
            int l = Integer.parseInt(br.readLine());

            int[][] map = new int[l][l];

            tokens = new StringTokenizer(br.readLine());
            int x1 = Integer.parseInt(tokens.nextToken());
            int y1 = Integer.parseInt(tokens.nextToken());

            tokens = new StringTokenizer(br.readLine());
            int x2 = Integer.parseInt(tokens.nextToken());
            int y2 = Integer.parseInt(tokens.nextToken());

            //나이트의 이동 방향 8방
            System.out.println(bfs(x1, y1, x2, y2, l));
        }
    }

    private static int bfs(int x1, int y1, int x2, int y2, int l) {
        int res = -1;
        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{x1, y1, 0});

        boolean[][] v = new boolean[l][l];
        v[x1][y1] = true;

        while (!q.isEmpty()){
            int[] c = q.poll();

            if(c[0] == x2 && c[1] == y2){
                res = c[2];
                break;
            }

            for (int d = 0; d < 8; d++) {
                int nx = c[0] + dir[d][0];
                int ny = c[1] + dir[d][1];

                if(!isRange(nx, ny, l) || v[nx][ny]) continue;
                v[nx][ny] = true;
                q.offer(new int[]{nx, ny, c[2]+1});
            }
        }
        return res;
    }


    static int[][] dir = {
            {-2, -1}, {-2, 1},
            {-1, -2}, {1, -2},
            {2, -1}, {2, 1},
            {-1, 2}, {1, 2}};

    private static boolean isRange(int x, int y, int l) {
        if (x < 0 || x >= l || y < 0 || y >= l) return false;
        return true;
    }
}

문제 링크

https://www.codetree.ai/training-field/frequent-problems/codetree-mon-bread/description?page=3&pageSize=20&username= 

접근 방법

위치 배열을 2차원 배열로 사용했다. [사람수][편의점/현위치]

한번 이동할때마다 이 사람이 베이스캠프에 배정되어야 하는지, 편의점에 도착했는지를 확인해야 한다.

자기 차례가 현재 시간보다 크면 더 이상 탐색할 필요가 없다.

이동할때에는 어느 방향으로 가야 하는지를 처음에 몰랐다. 스터디에서 bfs로 가야 하는 방향을 구하려면, 처음에 방향에 대한 값을 그대로 유지하면서 도착지까지 bfs로 구한다. 그래서 q에 넣을 때 처음 4방향이 범위에 맞고 갈 수 있는 방향인지 확인한 다음 큐에 모두 넣었다.

이 부분을 생각하지 못해서(그리고 그 외 코드 오류의 이유로) 44%에서 시간 초과가 났으나 결국 고쳤다!

편의점에 도착했는지 확인할 때,

if (pos[i][0].x == pos[i][1].x && pos[i][0].y == pos[i][1].y)

if (pos[i][0] == pos[i][1])

이 두개가 같은 동작이 되는 줄 알고 후자로 썼다가 메모리 초과가 생겼다. 자바에서 객체에 대한 비교는 메모리 주소를 비교하기 때문에 땡!

또한, 처음에는 베이스캠프를 전부 구해두고 시작하려 했는데 다른 부분과 겹쳐져 오류가 났다. 베이스캠프를 전부 구하고 시작해도 되는지 궁금하다. 다음에 시간이 날 때 한번 풀어봐야겠다.

코드

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

public class Main {
    static int N, M, map[][], finish;
    static Pos pos[][];
    static int[][] dir = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};

    static class Pos {
        int x, y, d;

        public Pos(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public Pos(int x, int y, int d) {
            this.x = x;
            this.y = y;
            this.d = d;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokens = new StringTokenizer(br.readLine());

        //입력 받기
        N = Integer.parseInt(tokens.nextToken()); //격자 크기
        M = Integer.parseInt(tokens.nextToken()); //사람 수
        map = new int[N][N]; //맵
        pos = new Pos[M][2]; //편의점 위치, 현재 위치

        //map input
        for (int i = 0; i < N; i++) {
            tokens = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(tokens.nextToken());
            }
        }

        //store input
        for (int i = 0; i < M; i++) {
            tokens = new StringTokenizer(br.readLine());
            pos[i][0] = new Pos(Integer.parseInt(tokens.nextToken()) - 1, Integer.parseInt(tokens.nextToken()) - 1);
        }

        int t = 0;
        finish = 0;
        while (finish < M) {
            move(t++);
        }
        System.out.println(t);

    }

    private static void move(int t) {
        //한 타임마다 모든 사람 이동
        for (int i = 0; i < M; i++) {
            //자기 차례가 되지 않아 격자 밖이라면 더이상 진행 안함
            if (i > t) return;
            //t == i이고 pos 현위치가 null이라면 베이스캠프 배정
            if (i == t && pos[i][1] == null) {
                getBaseCamp(i); //i번째 사람이 가려는 편의점에서 가장 가까운 베이스캠프 정함
            } else { //아니라면 최단 거리로 갈 방향 선택해서 이동
                if(pos[i][1] == null) continue; //이미편의점에 도착한 사람
                int d = goFast(i); //최단 거리로 갈 방향 구해옴
                //이동
                pos[i][1].x += dir[d][0];
                pos[i][1].y += dir[d][1];
                //편의점에 도착했는지 확인
                if (pos[i][0].x == pos[i][1].x && pos[i][0].y == pos[i][1].y) {
                    int cx = pos[i][0].x;
                    int cy = pos[i][0].y;
                    map[cx][cy] = 9; //맵에 방문 못하게 처리
                    pos[i][1] = null; //자신은 비움
                    finish++; //편의점에 도착한 사람 처리
                }
            }

        }

    }

    private static int goFast(int idx) { //현위치
        //현 위치에서 목적지 편의점까지 가장 빠른 방향을 구함
        Pos dest = pos[idx][0]; //도착하고자 하는 곳
        Pos start = pos[idx][1]; //현재 위치
        Deque<Pos> q = new ArrayDeque<>();
        boolean[][] v = new boolean[N][N];

        //4방향 전부 넣음
        for (int d = 0; d < 4; d++) {
            int nx = start.x + dir[d][0];
            int ny = start.y + dir[d][1];
            if(!isRange(nx, ny) || map[nx][ny] == 9) continue;
            q.offer(new Pos(nx, ny, d));
            v[nx][ny] = true;
        }

        int direction = -1;

        while (!q.isEmpty()) {
            Pos cur = q.poll();
            if (cur.x == dest.x && cur.y == dest.y) {
                //목적지 방향을 구함
                direction = cur.d;
                break;
            }

            for (int d = 0; d < 4; d++) {
                int nx = cur.x + dir[d][0];
                int ny = cur.y + dir[d][1];

                if (!isRange(nx, ny) || map[nx][ny] == 9 || v[nx][ny]) continue;
                q.offer(new Pos(nx, ny, cur.d)); //방향 처음 그대로 저장
                v[nx][ny] = true;
            }
        }
        return direction;
    }

    //베이스 캠프 정하기 : bfs, 주어진 방향 순서대로 이동 후 가장 먼저 도착하는 곳이 베이스캠프(상좌우하)
    private static void getBaseCamp(int idx) {
        Pos s = pos[idx][0];
        Deque<Pos> q = new ArrayDeque<>();
        q.offer(s);
        boolean[][] v = new boolean[N][N];
        v[s.x][s.y] = true;

        while (!q.isEmpty()) {
            Pos cur = q.poll();

            for (int d = 0; d < 4; d++) {
                int nx = cur.x + dir[d][0];
                int ny = cur.y + dir[d][1];

                if (!isRange(nx, ny) || map[nx][ny] == 9 || v[nx][ny]) continue;
                //0이면 다음 위치로
                if (map[nx][ny] == 0) {
                    q.offer(new Pos(nx, ny));
                    v[nx][ny] = true;
                }
                //1이면 베이스 캠프 선택 완료
                if (map[nx][ny] == 1) {
                    pos[idx][1] = new Pos(nx, ny); //현재 위치 갱신
                    map[nx][ny] = 9; //맵에서 사용 못하게 처리
                    return;
                }
            }
        }
    }

    private static boolean isRange(int x, int y) {
        if (x < 0 || y < 0 || x >= N || y >= N) return false;
        return true;
    }

}

문제링크

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

접근 방법

1부터 10000까지 주어진 숫자를 만든다

10000은 10001이 되고, 9999는 9999+9+9+9+9 = 10035이 되기 때문에 숫자 배열을 11000까지 미리 생성해줬다.

만들어진 숫자를 인덱스로 잡아 값을 증가시켜준다.

1부터 10000까지 탐색하면서 0인 곳을 출력하면 됨.

코드

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        int sum;
        //9999 -> 9999+9+9+9+9 = 10035
        int[] arr = new int[11000];
        for (int i = 1; i <= 10000; i++) {
            //1~10000까지 숫자를 다 만듦
            sum = 0;
            String str = Integer.toString(i);
            for (int j = 0; j < str.length(); j++) {
                sum += str.charAt(j) - '0';
            }
            sum += i;
            arr[sum]++;
        }
        for (int i = 1; i <= 10000; i++) {
            if(arr[i] == 0){
                sb.append(i).append("\n");
            }
        }
        
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/150368

접근 방법

1. 이모티콘 마다 할인율을 dfs로 구함
2. 사용자 수만큼 반복
   1. 이모티콘 수만큼 반복
      • 이모티콘 할인율 ≥ 사용자 라면 할인율을 계산해서 지불할 금액에 더함
   2. 지불할 금액 ≥ 제한금액이면 이모티콘 플러스 가입
   3. 아니라면 판매액에 지불할 금액 더함
3. 결과값이랑 비교
   1. 이모티콘 플러스 사용자가 많다면 갱신
   2. 이모티콘 플러스 사용자가 같다면 판매액이 더 많은 것 갱신

블라인드 코테에선 못 풀었는데 끝나고 반년 뒤에 푸니까 풀렸다...

할인율을 배열로 선언할 필요 없이 for문의 i를 40 30 20 10으로 줄어들게 해도 된다.

이렇게 작성하는게 더 깔끔하다는걸 우리의 스터디 알고신에게 배움

이모티콘 금액 계산하다가 이모티콘 플러스 가입 금액이 넘으면 반복문 탈출해도 된다. 여기서 시간을 단축시킬 수 있다고 한다. 이것 또한 알고신의 첨언...

코드

class Solution {
    static int len, resEmo, resSell;
    static int[] r = {40, 30, 20, 10};
    static int e[], u[][];
    public static int[] solution(int[][] users, int[] emoticons) {
        e = emoticons;
        u = users;
        len = emoticons.length;
        resEmo = 0;
        resSell = 0;

        //이모티콘마다 할인율 10, 20, 30, 40 중 선택
        dfs(0, emoticons.length, new int[emoticons.length]);

        System.out.println(resEmo+" "+resSell);

        return new int[]{resEmo, resSell};
    }
    private static void dfs(int dept, int len, int[] s){
        //종료조건
        if(dept == len){
            calcMember(s);
            return;
        }

        //이모티콘 선택
        for (int i = 0; i < 4; i++) {
            s[dept] = r[i]; //할인율 선택
            dfs(dept+1, len, s);
        }
    }

    private static void calcMember(int[] s) {

        int emoPlus = 0;
        int totalSell = 0;

        //사용자 수만큼 for, 구매할 사람 선택
        for(int[] user : u){
            int personRate = user[0];
            int limitMoney = user[1];

            //한 사람이 지불할 가격
            int money = 0;
            //살 이모티콘 선택
            for (int i = 0; i < len; i++) {
                if(s[i] >= personRate){ //일정 비율 이상 할인이라면
                    //살 돈 계산
                    money += e[i] * (100-s[i]) / 100;
                }
            }//살 이모티콘 계산 끝

            //이모티콘 플러스 가입 여부 확인
            if(money >= limitMoney){
                //이모티콘 플러스 가입
                emoPlus++;
            }else{
                totalSell += money; //판매 총액 갱신
            }
        }

        //최종 이모티콘 플러스 가입자, 판매총액 비교
        if(resEmo < emoPlus){
            resEmo = emoPlus;
            resSell = totalSell;
        }else if(resEmo == emoPlus && resSell < totalSell){
            resSell = totalSell;
        }
    }
}

문제 링크

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

접근 방법

dfs를 사용한다.
종료 조건은 A,B가 같은 경우 최소 횟수를 갱신하고 리턴
dfs를 타는 부분은 2를 곱할때, 1을 뒤에 붙일때.

input이 10^9까지 들어오기 때문에 long으로 처리했다.
백트래킹은 횟수와 A의 크기를 비교해서 처리했다.

코드

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

public class Main {

    static int res;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokens = new StringTokenizer(br.readLine());

        Long A = Long.parseLong(tokens.nextToken());
        Long B = Long.parseLong(tokens.nextToken());

        res = Integer.MAX_VALUE;

        dfs(A, B, 1);

        System.out.println(res == Integer.MAX_VALUE ? -1 : res);
    }
    private static void dfs(long A, long B, int cnt) {
        if (res < cnt || A > B) { //백트래킹
            return;
        }

        if (B == A) {
            res = Math.min(res, cnt);
            return;
        }
        //2를 곱함
        dfs(A * 2, B, cnt + 1);
        //끝에 1을 붙임
        dfs(Long.parseLong(Long.toString(A) + "1"), B, cnt + 1);
    }
}

문제 링크

https://www.codetree.ai/training-field/frequent-problems/tail-catch-play/description?page=3&pageSize=20&username=nnindd&discussionRowsPerPage=5&discussionPage=1

접근 방법

큰 순서는 아래와 같다.

• 1의 위치를 리스트에 저장
• k번 게임 실행
  • 이동 (M만큼 for)
    • 바뀐 1의 위치 갱신
  • 공 던지는 4분면, 행, 열, 방향 구하기
  • 공 던지기
    • 맞음
      • 맞았다면 몇번째 사람인지 구하기
        • 맵의 크기만큼 반복문 돌면서 1인 곳 찾기
        • 1이면 해당 팀원 위치 리스트 받아오기
        • 그 리스트에 맞은 사람 위치 있는지 확인
        • 있으면 맵에서 1, 3 변경
        • 있으면 머리 리스트에서 1 위치 갱신
        • 인덱스 제곱 계산해서 반환
    • 안 맞음
      • 공 멈추기 않고 던지기

길다..
우욱..
깔끔하게 작성하려고 함수를 다 빼면서 작성하다가 헷갈려서 생각나는대로 적었다.
input이 적기 때문에 전부 확인해봐도 되었고, 시간복잡도는 O(K*N^2)라니 1000*20^2면.. 할만함

어려웠던 부분

공 던지는 위치를 구하는게 어려웠다.

일정한 크기에 대해서 지정을 하려면 % 연산이 필요하다는걸 알겠는데 어떻게 계산을 해야 할지 몰라서 처음엔 풀지 못했다.

일단 4분면 중 한곳에 위치할 수 있게 하고, 방향에 따라서 N 안에서 어디에 위치하는지...

/ 와 % 를 사용하면 된다는걸 아는데.. 아는데! 항상 헷갈린다..

더 많이 풀어봐야함

지나갈 수 있는 길이 1 2 2 3 4 4 4 이런 형식이 아니라 1 2 2 2 2 3 으로 끝나는 경우를 생각해봐야 한다.

1이 이동할 땐 4인 곳으로 가는 것이 아니라 2가 아닌 곳으로 간다고 생각해야 한다.

이 생각을 듣고 아득해짐......

코드

import java.io.*;
import java.util.*;

public class Main {

    static int N, M, K, map[][], total;
    static ArrayList<int[]> first; //1의 위치
    static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer tokens = new StringTokenizer(br.readLine());
        N = Integer.parseInt(tokens.nextToken()); //격자 크기
        M = Integer.parseInt(tokens.nextToken()); //팀의 개수
        K = Integer.parseInt(tokens.nextToken()); //라운드 수

        map = new int[N][N]; //맵
        total = 0;

        first = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            tokens = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(tokens.nextToken());
                if (map[i][j] == 1) { //1의 위치 저장
                    first.add(new int[]{i, j});
                }
            }
        }//end input

        for (int i = 0; i < K; i++) {
            total += play(i);
        }

        bw.write(total + "");
        bw.flush();
        bw.close();
    }

    private static int play(int k) {
        //이동
        for (int i = 0; i < M; i++) {
            int[] cur = move(first.get(i));
            //바뀐 1의 위치 갱신해주기
            first.set(i, cur);
        }

        //공던짐
        int[] rcd = getRowColDirection(k);
        int area = rcd[0];
        int row = rcd[1];
        int col = rcd[2];
        int d = rcd[3];

        int x = row;
        int y = col;
        int temp = 0;
        while (isRange(x, y)) { //범위 안 벗어날때까지
            if (map[x][y] != 0 && map[x][y] != 4) {
                //맞은 사람 몇번째인지 구하기 + 점수 갱신 + 머리 꼬리 바꾸기
                temp = checkIndex(x, y);
                break;
            }
            //안 맞았으면 다음방향
            x += dir[d][0];
            y += dir[d][1];
        }
        return temp;
    }

    private static int checkIndex(int x, int y) {
        //몇번째 사람인지 구하기

        ArrayList<int[]> list;

        //1인 부분 확인
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] != 1) continue;

                //이 팀원 리스트 불러옴
                list = getTeamPosition(new int[]{i, j});

                //이 팀원 중 이사람이 있는지 확인
                for (int k = 0; k < list.size(); k++) {
                    if (list.get(k)[0] == x && list.get(k)[1] == y) {
                        //머리 꼬리 맵에서 바꾸기
                        int[] front = list.get(0);
                        int[] back = list.get(list.size()-1);
                        int temp = map[front[0]][front[1]];
                        map[front[0]][front[1]] = map[back[0]][back[1]];
                        map[back[0]][back[1]] = temp;

                        //머리 리스트에 머리 변경
                        for (int l = 0; l < first.size(); l++) {
                            int[] head = first.get(l);
                            if(head[0] == front[0] && head[1] == front[1]){
                                first.set(l, back); //꼬리를 머리로 바꿈
                            }
                        }
                        //점수 반환
                        return (k + 1) * (k + 1);
                    }
                }
            }
        }
        return 0;
    }

    private static int[] getRowColDirection(int k) {
        //던진 위치에 따라서 행, 열, 방향을 구함
        // 좌 하 우 상 순서로 0 1 2 3
        int area, row, col, dir; //4변 중 위치, 어느 행/열에 있는지, 공던지는 방향

        area = (k / N) % 4; //4변 중 어디인지 구하기

        if (area == 0) {
            col = 0;
            row = k % N;
            dir = 3;
        } else if (area == 1) {
            row = N - 1;
            col = k % N;
            dir = 0;
        } else if (area == 2) {
            row = N - (k % N) - 1;
            col = N - 1;
            dir = 2;
        } else {
            row = 0;
            col = N - (k % N) - 1;
            dir = 1;
        }

        return new int[]{area, row, col, dir};
    }

    private static int[] move(int[] n1) {
        //팀원 리스트 구함
        ArrayList<int[]> list = getTeamPosition(n1);

        //한명씩 이동 -> 첫번째만 갈 곳 정하고 그 다음부턴 이전의 위치로 변경
        //첫번째 이동
        int[] one = n1;//첫번째가 이동한 위치 저장 (1이 3으로 이동했을 때 4로 덮어씌워지는것 방지)
        for (int d = 0; d < 4; d++) {
            int nx = n1[0] + dir[d][0];
            int ny = n1[1] + dir[d][1];

            //범위 내이고 2가 아닐때
            if (!isRange(nx, ny) || map[nx][ny] == 0) continue;
            if (map[nx][ny] != 2) {
                map[nx][ny] = map[n1[0]][n1[1]]; //1번은 0,2가 아닌 곳으로 이동
                one = new int[]{nx, ny};
                break; //더 볼 것 없음
            }
        }

        int[] next = n1; //다음 사람이 이동할 곳
        //남은 위치 이동
        for (int i = 1; i < list.size(); i++) {
            //위치 이동
            int[] cur = list.get(i);
            map[next[0]][next[1]] = map[cur[0]][cur[1]]; //앞의 사람이 옮겨간 자리에 채우기
            if (i == list.size() - 1) {
                map[next[0]][next[1]] = 3; //마지막 값이라면 1이 덮어씌운 값으로 들어가는 것 방지3 처리
            }
            map[cur[0]][cur[1]] = 4; //자신이 있던 곳 빈곳 처리
            next = cur; //다음 채울 곳 갱신
        }
        //1이 3으로 이동했을 때 마지막에 4로 덮어 씌워지는 것 방지
        map[one[0]][one[1]] = 1;

        //1의 위치 갱신
        return one;
    }

    private static ArrayList<int[]> getTeamPosition(int[] n1) {
        Queue<int[]> q = new ArrayDeque<>(); //방문확인
        q.offer(n1);
        boolean[][] v = new boolean[N][N];
        v[n1[0]][n1[1]] = true;
        ArrayList<int[]> list = new ArrayList<>(); //팀들 위치 저장 리스트
        list.add(n1);

        //bfs로 팀원 위치 구함
        while (!q.isEmpty()) {
            int[] cur = q.poll();

            for (int d = 0; d < 4; d++) {
                int nx = cur[0] + dir[d][0];
                int ny = cur[1] + dir[d][1];

                if (!isRange(nx, ny) || map[nx][ny] == 0 || map[nx][ny] == 4 || v[nx][ny]) continue;
                //나의 값보다 같거나 하나 클때만 이동
                if ((map[cur[0]][cur[1]] == 1 && map[nx][ny] == 2)
                        || (map[cur[0]][cur[1]] == 2 && map[cur[0]][cur[1]] <= map[nx][ny])) {
                    //1이면 2로만 가고, 2라면 같거나 큰곳으로만
                    v[nx][ny] = true;
                    q.offer(new int[]{nx, ny});
                    list.add(new int[]{nx, ny}); //팀원 위치 저장
                }
            }
        }
        return list;
    }

    private static boolean isRange(int x, int y) {
        if (x < 0 || y < 0 || x >= N || y >= N) return false;
        return true;
    }


}

문제 링크

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

접근 방법

처음엔 어렵게 생각했는데 30의 배수를 구하는 방법을 생각하면 된다.

1. 끝은 0으로 끝나야 함
2. 각 자리수의 합이 3의 배수여야 한다

그래서 입력 받은 수를 문자열로 받아 char 배열로 만들고 정렬했다.
내림차순으로 접근해서 가장 큰 수를 만들었음.

코드

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

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        //0이 포함되어야 30의 배수를 만들 수 있다.
        //각 자리의 합이 3의 배수여야 30의 배수를 만들 수 있다.

        //1. 입력받은 문자열을 0~9까지의 카운트 배열에 입력하고 총합 계산
        String num = br.readLine();

        char[] arr = num.toCharArray();
        Arrays.sort(arr);

        int sum = 0;
        StringBuilder sb = new StringBuilder();

        for (int i = num.length() - 1; i >= 0; i--) {
            sum += arr[i] - '0';
            sb.append(arr[i] - '0');
        }

        //2. 0을 포함하는지, 총합이 3의 배수인지 확인
        System.out.println(num.contains("0") && sum % 3 == 0 ? sb : -1);
    }

}

문제 링크

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

접근 방법

음~
잘못 생각한 방법

• 거리 중 가장 싼 도시를 고름
• 그 도시에서 남은 거리 모두 충전
• 다른 거리는 다음 도시로 가기 위해 필요한 거리 만큼만 저장

➡️ 이랬더니 17점 나옴

올바른 풀이

• 순서대로 탐색하면서 이전보다 싸면 최소값으로 갱신
• 해당 도시의 거리만큼 가장 싼 곳에서 충전

처음에 첫번째 도시를 최소값으로 설정하고, 두번째 도시로 가기 위한 비용을 설정해준다.

for문은 2번째 도시부터 N만큼 탐색한다.

탐색하면서 현재 주유비용이 이전보다 싸다면 최소값을 갱신해준다.

다음 도시로 가기 위해 해당 거리는 꼭 충전을 해줘야 하기 때문에 현재 최소값으로 주유한다.

input 반복문을 두번 돌리고 마지막에 다시 반복문을 돌면서 탐색을 했는데, 도시 주유 비용 입력 받으면서 한번에 처리 해도 돼서 코드를 수정했다.

시간은 O(N)이 됨.

코드

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));

        int N = Integer.parseInt(br.readLine());
        StringTokenizer tokens = new StringTokenizer(br.readLine());

        //도시 사이 거리
        long[] dist = new long[N - 1];
        for (int i = 0; i < N - 1; i++) {
            dist[i] = Integer.parseInt(tokens.nextToken());
        }

        tokens = new StringTokenizer(br.readLine());
        int cost = Integer.parseInt(tokens.nextToken()); //가장 처음 값

        //초기값 설정. 처음 도시는 다음 거리만큼 충전해야 함
        long min = cost;
        long result = min * dist[0];

        //두번째 도시부터 설정
        for (int i = 1; i < N-1; i++) {
            cost = Integer.parseInt(tokens.nextToken());
            min = cost < min ? cost : min; //이전 값이랑 비교해서 싼 값 저장
            result += (min * dist[i]);
        }// end input

        System.out.println(result);

    }
}

문제 링크

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

접근 방법

처음에 문제 이해를 못했다.

1차 점수로 정렬해서 1등을 뽑고 2차 첨수로 정렬했을 때 1등의 2차 점수보다 낮은 사람을 다 탈락시키면 되는건가 싶었는데 아니었다.

정올에서 같은 문제가 있어 반례를 확인해볼 수 있었는데, 다음과 같다

input
10
9 1
5 7
1 8
2 4
10 5
4 10
7 6
3 2
6 9
8 3

output
4

나
7

잘못 생각했던 부분은 1차 점수로 정렬하고 2차 점수로 재정렬하는 것이 아니었다.

1차 기준으로 정렬 후 2차에서 2차 점수가 가장 높은 것을 갱신해나가면서 그보다 낮은 지원자들을 빼는 방법이었다.

코드

package BOJ;

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

public class Main_1946_신입사원 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokens;
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());
        int N;

        while (T-->0){
            N = Integer.parseInt(br.readLine());

            int[][] arr = new int[N][2];

            for (int i = 0; i < N; i++) {
                tokens = new StringTokenizer(br.readLine());
                //서류, 면접
                arr[i][0] = Integer.parseInt(tokens.nextToken());
                arr[i][1] = Integer.parseInt(tokens.nextToken());
            }

            //서류 기준 오름차순 정렬
            Arrays.sort(arr, (a, b) -> a[0]-b[0]);

            int cnt = N;
            int max = arr[0][1]; //서류 1등의 면접 점수 저장
            for (int i = 1; i < N; i++) {
                if(arr[i][1] < max){//현재 1등의 등수보다 i의 면접 등수가 높으면 최대값 변경
                    max = arr[i][1];
                }else{ //현재 1등의 면접 점수보다 낮으면 선발 안 함
                    cnt--;
                }
            }
            sb.append(cnt).append("\n");
        }
        System.out.println(sb);
    }
}

뿌듯함을 느꼈으나 시간이 이렇게까지 많이 걸린다고? 싶었다.

어떤 힘을 조금 빌린 결과 정렬이 꼭 필요하지 않다는 것을 알게 되었다.

1차인 서류 등수를 인덱스로 사용하고 2차 면접 점수를 값으로 사용하면 정렬할 필요가 없어진다.

이런 생각 해내는 뇌..당장훔쳐...

코드2

package BOJ;

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

public class Main_1946_신입사원 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokens;
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());
        int N;

        while (T-->0){
            N = Integer.parseInt(br.readLine());

            int[] arr = new int[N+1];

            for (int i = 0; i < N; i++) {
                tokens = new StringTokenizer(br.readLine());
                //서류, 면접
                int idx = Integer.parseInt(tokens.nextToken());
                int val = Integer.parseInt(tokens.nextToken());

                arr[idx] = val;
            }

            //서류 기준 오름차순 정렬
            int top = arr[1];
            int cnt = 1; //서류 1등

            for (int i = 2; i <= N; i++) {
                if(arr[i] < top){
                    top = arr[i];
                    cnt++;
                }
            }
            sb.append(cnt).append("\n");
        }
        System.out.println(sb);
    }
}

만족

문제 링크

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

접근 방법

3번 나누고 나머지를 T에 갱신시켜주면 되는 문제.

간단해서 할 설명이 없다.

랭크 꺼놓고 풀었더니 브론즈였을때의 허무함...

코드

package BOJ;

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

public class Main_10162_전자레인지 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());
        int[] arr = {300, 60, 10};

        for (int i = 0; i < 3; i++) {
            sb.append(T / arr[i]).append(" ");
            T %= arr[i];
        }

        if (T != 0) {
            sb.delete(0, sb.length()).append(-1);
        }
        System.out.println(sb);

    }
}