초딩코보 루피

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

public class Main {
    static int arr[], parent[];
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int N = Integer.parseInt(st.nextToken()), M = Integer.parseInt(st.nextToken());
        arr = new int[N]; parent = new int[N];
        for(int i=0;i<N;i++) {
            arr[i] = Integer.parseInt(bf.readLine());
            parent[i] = i;
        }
        for(int i=0;i<M;i++) {
            st = new StringTokenizer(bf.readLine());
            int a = Integer.parseInt(st.nextToken())-1, b = Integer.parseInt(st.nextToken())-1;
            int fa = find(a), fb = find(b);
            
            if(fa==fb) {
                bw.write(Integer.toString(arr[fa])+"\n");
            } else if(fa < fb) {
                parent[fb] = fa;
                arr[fa] += arr[fb];
                arr[fb] = 0;
                bw.write(Integer.toString(arr[fa])+"\n");
            } else {
                parent[fa] = fb;
                arr[fb] += arr[fa];
                arr[fa] = 0;
                bw.write(Integer.toString(arr[fb])+"\n");
            }
        }
        bw.flush();
    }
    static int find(int a) {
        if(a == parent[a]) {
            return a;
        }
        return parent[a] = find(parent[a]);
    }
}

import java.util.*;
import java.io.*;
 
public class Main {    
 
    static int n, k, d[]; 
    
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        int tc = Integer.parseInt(bf.readLine());
 
        for(int t=0; t<tc; t++) {
            st = new StringTokenizer(bf.readLine());
            n = Integer.parseInt(st.nextToken());
            k = Integer.parseInt(st.nextToken());
            d = new int[n+1];
 
            List<List<Integer>> list = new ArrayList<List<Integer>>();
            for(int i=0; i<n+1; i++) {
                list.add(new ArrayList<Integer>());
            }
            
            int[] indegree = new int[n+1];
 
            st = new StringTokenizer(bf.readLine());
            for(int i=1; i<=n; i++) {
                d[i] = Integer.parseInt(st.nextToken());
            }
                    
            for(int i=0; i<k; i++) {
                st = new StringTokenizer(bf.readLine());
    
                int v1 = Integer.parseInt(st.nextToken()),
                v2 = Integer.parseInt(st.nextToken());
    
                list.get(v1).add(v2);
                indegree[v2]++;
            }
 
            int w = Integer.parseInt(bf.readLine());
    
            topologicalSort(indegree, list, w);    
        }
    }
 
    static void topologicalSort(int[] indegree, List<List<Integer>> list, int w) {
        Queue<Integer> q = new LinkedList<Integer>();
        int[] result = new int[n+1];
 
        for(int i=1; i<=n; i++) {
            result[i] = d[i];
 
            if(indegree[i] == 0)
                q.offer(i);
        }
 
        while(!q.isEmpty()) {
            int node = q.poll();
 
            for(Integer i : list.get(node)) {
                result[i] = Math.max(result[i], result[node] + d[i]);
                indegree[i]--;
 
                if(indegree[i] == 0)
                    q.offer(i);
            }
        }
 
        System.out.println(result[w]);
    }
}

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
typedef pair<int, int> p;
 
int n, answer;
int highest, lowest;
int qcnt[1001];
vector<int> qual;
 
void init() {
    int input;
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        cin >> input;
        if (qcnt[input] == 0) qual.push_back(input);
        qcnt[input]++;
    }
 
    sort(qual.begin(), qual.end());
 
    lowest = 0;
    highest = qual.size() - 1;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    init();
 
    while (1) {
        if (lowest > highest) break;
        int low_cnt = qcnt[qual[lowest]];
        int high_cnt = qcnt[qual[highest]];
        if (lowest == highest) {
            answer += qual[highest] * high_cnt;
            qcnt[highest] = 0;
            lowest++;
            continue;
        }
        if (low_cnt < high_cnt) {
            answer += qual[highest] * low_cnt * 2;
            qcnt[qual[highest]] -= low_cnt;
            qcnt[qual[lowest]] = 0;
            lowest++;
        }
        else {
            answer += qual[highest] * high_cnt * 2;
            qcnt[qual[lowest]] -= high_cnt;
            qcnt[qual[highest]] = 0;
            highest--;
        }
    }
 
    printf("%d\n", answer);
 
    return 0;
}

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

public class Main {

    static class Meeting implements Comparable<Meeting> {
        int start, end, people;

        Meeting(int start, int end, int people) {
            this.start = start;
            this.end = end;
            this.people = people;
        }

        @Override
        public int compareTo(Meeting o) {
            return this.end - o.end; // 종료 시간 기준 정렬
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());

        Meeting[] meetings = new Meeting[n];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(bf.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int people = Integer.parseInt(st.nextToken());
            meetings[i] = new Meeting(start, end, people);
        }

        // 종료 시간 기준 정렬
        Arrays.sort(meetings);

        // DP 배열 및 종료 시간 배열
        int[] dp = new int[n];
        int[] endTimes = new int[n];

        for (int i = 0; i < n; i++) {
            endTimes[i] = meetings[i].end; // 종료 시간만 저장
        }

        dp[0] = meetings[0].people; // 첫 회의 인원 초기화

        for (int i = 1; i < n; i++) {
            // 현재 회의 인원
            dp[i] = meetings[i].people;

            // 이전 회의 중 겹치지 않는 가장 마지막 회의 찾기 (이분 탐색)
            int idx = binarySearch(endTimes, meetings[i].start);
            if (idx != -1) {
                dp[i] += dp[idx];
            }

            // 이전 최대값과 비교
            dp[i] = Math.max(dp[i], dp[i - 1]);
        }

        System.out.println(dp[n - 1]);
    }

    // 이분 탐색: 종료 시간이 target 이하인 가장 마지막 인덱스를 찾음
    private static int binarySearch(int[] endTimes, int target) {
        int left = 0, right = endTimes.length - 1;
        int result = -1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (endTimes[mid] <= target) {
                result = mid; // 가능한 인덱스 갱신
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return result;
    }
}

문제 캡처

소스 코드

import java.io.*;
import java.util.*;
import java.util.Map.Entry;

public class Main {

    static Comparator<Integer> comparator(Map<Integer, Integer> map) {
        return (key1, key2) -> {
            int value1 = map.get(key1), value2 = map.get(key2);
            if(value1 == value2) {
                return key1 - key2;
            }
            return value1 - value2;
        };
    };

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int r = Integer.parseInt(st.nextToken())-1,
        c = Integer.parseInt(st.nextToken())-1,
        k = Integer.parseInt(st.nextToken());

        int[][] arr = new int[101][101];

        for(int i=0;i<3;i++) {
            st = new StringTokenizer(bf.readLine());
            for(int j=0;j<3;j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int time = 0;
        int rowCnt = 3, colCnt = 3;
        while(arr[r][c] != k && time <= 100) {
            time++;
            if(rowCnt >= colCnt) {
                int col = colCnt;
                //R연산
                for(int i=0;i<rowCnt;i++) {
                    Map<Integer, Integer> freqMap = new HashMap<>();
                    //행 연산 실행
                    for(int j=0;j<colCnt;j++) {
                        if(arr[i][j] == 0) continue;
                        freqMap.put(arr[i][j], freqMap.getOrDefault(arr[i][j], 0)+1);
                    }
                    TreeMap<Integer, Integer> sortMap = new TreeMap<>(comparator(freqMap));
                    sortMap.putAll(freqMap);
                    int nowColCnt = sortMap.size()*2;
                    for(int j=0;j<nowColCnt;j+=2) {
                        Entry<Integer, Integer> value = sortMap.pollFirstEntry();
                        arr[i][j] = value.getKey();
                        arr[i][j+1] = value.getValue();
                    }
                    for(int j=nowColCnt;j<colCnt;j++) {
                        arr[i][j] = 0;
                    }
                    col = Math.max(col, nowColCnt);
                }
                colCnt = col;
            } else {
                int row = rowCnt;
                //C연산
                for(int j=0;j<colCnt;j++) {
                    Map<Integer, Integer> freqMap = new HashMap<>();
                    //열 연산 실행
                    for(int i=0;i<rowCnt;i++) {
                        if(arr[i][j] == 0) continue;
                        freqMap.put(arr[i][j], freqMap.getOrDefault(arr[i][j], 0)+1);
                    }
                    TreeMap<Integer, Integer> sortMap = new TreeMap<>(comparator(freqMap));
                    sortMap.putAll(freqMap);
                    int nowRowCnt = sortMap.size()*2;
                    for(int i=0;i<nowRowCnt;i+=2) {
                        Entry<Integer, Integer> value = sortMap.pollFirstEntry();
                        arr[i][j] = value.getKey();
                        arr[i+1][j] = value.getValue();
                    }
                    for(int i=nowRowCnt;i<rowCnt;i++) {
                        arr[i][j] = 0;
                    }
                    row = Math.max(row, nowRowCnt);
                }
                rowCnt = row;
            }
        }
        
        System.out.println(time>100 ? -1 : time);

    }
}

문제 캡처

소스 코드

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

public class Main {
    static class Loc {
        int r, c;
        
        Loc(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
    static List<Loc> viruses = new ArrayList<>();
    static int N, M, dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}, arr[][];
    static boolean[][] visited;
    static int minTime = Integer.MAX_VALUE;
    static int emptyCount = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new int[N][N];
        for(int i=0;i<N;i++) {
            st = new StringTokenizer(bf.readLine());
            for(int j=0;j<N;j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                if(arr[i][j] == 2) {
                    viruses.add(new Loc(i, j));
                } else if(arr[i][j] == 0) {
                    emptyCount++;
                }
            }
        }

        activateVirus(-1, 0, new int[M]);
        System.out.println(minTime == Integer.MAX_VALUE ? -1 : minTime);
    }

    private static void activateVirus(int index, int cnt, int[] selected) {
        if(cnt == M) {
            getTime(selected);
            return;
        }

        for(int i=index+1;i<viruses.size();i++) {
            selected[cnt] = i;
            activateVirus(i, cnt+1, selected);
        }
    }

    private static void getTime(int[] selected) {
        Queue<Loc> queue = new ArrayDeque<>();
        visited = new boolean[N][N];
        int[][] times = new int[N][N];
        int infected = 0;
        int maxTime = 0;

        // 선택된 바이러스 위치 큐에 넣기
        for(int i : selected) {
            Loc virus = viruses.get(i);
            queue.offer(virus);
            visited[virus.r][virus.c] = true;
        }

        while(!queue.isEmpty()) {
            Loc cur = queue.poll();
            
            for(int d=0;d<4;d++) {
                int nx = cur.r + dx[d];
                int ny = cur.c + dy[d];
                
                if(isInRange(nx, ny) && !visited[nx][ny] && arr[nx][ny] != 1) {
                    visited[nx][ny] = true;
                    times[nx][ny] = times[cur.r][cur.c] + 1;
                    queue.offer(new Loc(nx, ny));
                    
                    if(arr[nx][ny] == 0) {
                        infected++;
                        maxTime = Math.max(maxTime, times[nx][ny]);
                    }
                }
            }
        }

        // 모든 빈 칸이 감염되었는지 확인
        if(infected == emptyCount) {
            minTime = Math.min(minTime, maxTime);
        }
    }

    private static boolean isInRange(int i, int j) {
        return 0 <= i && i < N && 0 <= j && j < N;
    }
}

문제 캡처

소스 코드

#include <iostream>
#include <string>
using namespace std;

int main() {
    string s;
    cin >> s;
    
    int count = 0;
    for (size_t i = 0; i < s.size(); i += 3) {
        string chunk = s.substr(i, 3);
        string target = "PER";
        for (int j = 0; j < 3; ++j) {
            if (chunk[j] != target[j]) {
                ++count;
            }
        }
    }

    cout << count << endl;
    return 0;
}

Comment…💭

문제 캡처

소스 코드

package baekjoon;

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

public class 양치기꿍_3187 {
    static char[][] map;
    static boolean[][] visited;
    static int R, C, vCnt, kCnt, dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
    static class Loc {
        int x, y;

        Loc(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    static Queue<Loc> queue;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        R = Integer.parseInt(st.nextToken()); C = Integer.parseInt(st.nextToken());
        map = new char[R][C]; visited = new boolean[R][C];

        for(int i=0;i<R;i++) {
            map[i] = bf.readLine().toCharArray();
        }

        int vAns = 0, kAns = 0;

        for(int i=0;i<R;i++) {
            for(int j=0;j<C;j++) {
                if(!visited[i][j] && map[i][j] != '#') {
                    visited[i][j] = true;
                    vCnt = 0; kCnt = 0;
                    if(map[i][j] == 'v') vCnt++;
                    if(map[i][j] == 'k') kCnt++;

                    queue = new ArrayDeque<>();
                    queue.offer(new Loc(i, j));

                    while(!queue.isEmpty()) {
                        Loc loc = queue.poll();
                        for(int idx = 0; idx < 4; idx++) {
                            int x = loc.x + dx[idx], y = loc.y + dy[idx];
                            if(!isInRange(x, y)) continue;
                            if(!visited[x][y]) {
                                visited[x][y] = true;
                                if(map[x][y] == '#') continue;
                                queue.offer(new Loc(x, y));
                                if(map[x][y] == 'v') vCnt++;
                                if(map[x][y] == 'k') kCnt++;
                            }
                        }
                    }
                    
                    if(kCnt > vCnt) {
                        kAns += kCnt;
                    } else {
                        vAns += vCnt;
                    }
                }
            }
        }
        System.out.println(kAns+" "+vAns);
    }
    static boolean isInRange(int x, int y) {
        return 0 <= x && x < R && 0 <= y && y < C;
    }

}

Comment…💭

• bfs만 돌리면 된다!
• 좀만 수정하면 코드길이와 메모리를 줄일 수 있을 것 같지만 시간이없다!