Pearlii-Log

문제 풀이 날짜: 2023.09.25
포스트 작성일: 2023.09.30

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

문제 출처

백준 온라인 저지 2668번: 숫자고르기 (골드5)

키워드

그래프, 사이클 찾기

풀이 접근법

• 같은 집합을 형성함 → 주어진 정보를 그래프로 나타낸다면 사이클을 형성한다.
• 따라서 사이클을 형성하는 노드의 번호들과 개수를 찾는다.
  • 이 문제는 한 노드 당 연결된 정점이 단 한개만 존재한다. (1:1 관계)
  • 그렇기 때문에 그래프를 연결리스트가 아니라 아니라 배열로 정의해도 되며, 이 편이 훨씬 풀이가 간단하다.
• 시작점부터 방문 체크를 하고 DFS를 들어가는데...
  • 이 때, 방문했던 점을 다시 방문했다면 && 해당 정점이 시작정점과 동일하다면 사이클을 형성하는 것이다.
  • 해당 정점을 결과 리스트에 넣어준다. 한 번 DFS를 끝냈다면 다른 사이클을 찾을 수 있도록 visited를 원복시켜준다. 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {

	private static int N;
	private static int[] graph;

	private static boolean[] visited;

	private static List<Integer> result = new ArrayList<>();

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

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

		graph = new int[N + 1];
		visited = new boolean[N + 1];

		int target = 0;
		for (int i = 1; i <= N; i++) {
			target = Integer.parseInt(br.readLine());
			graph[i] = target; //한 노드에 다른 하나의 노드만 대응 => 배열로 정의 가능
		}

		for (int u = 1; u <= N; u++) {
			visited[u] = true; //시작점
			findCycle(u, u);
			visited[u] = false;
		}

		Collections.sort(result);
		StringBuilder sb = new StringBuilder();
		for (int n : result) {
			sb.append(n).append("\n");
		}

		System.out.println(result.size());
		System.out.println(sb.toString());
	}

	private static void findCycle(int start, int curr) {
		if(!visited[graph[curr]]) {
			visited[graph[curr]] = true;
			findCycle(start, graph[curr]);
			visited[graph[curr]] = false;
		}
		if(start == graph[curr]) { //시작점으로 다시 되돌아왔다면
			result.add(start); //사이클 발생 => 결과 리스트에 추가
		}
	}
}

참고한 링크

https://moonsbeen.tistory.com/176

문제 풀이 날짜: 2023.09.25
포스트 작성일: 2023.09.30

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

문제 출처

백준 온라인 저지 14502번: 연구소 (골드4)

키워드

백트래킹(조합), BFS

풀이 접근법

• 백트래킹(가지치기) + BFS 문제
  •  3 ≤ N, M ≤ 8 이므로 최대 64개의 칸 중에서 3개의 칸을 선정한다.
  • 즉, 재귀의 depth가 3으로 고정된다. ⇒ 입력이 커도 재귀 백트래킹이 가능한 사례
  • 항상 3개의 벽을 세울 수 있는 경우만 입력으로 주어진다.
• 조합으로 벽을 3개씩 세울 때마다 감염되지 않은 칸이 몇 개인지 BFS로 센다. (flood fill)
• 주의: 벽에 막혀서 방문하지 못한 칸이 존재하더라도(false) 해당 칸의 숫자가 0이면 안전지역이다.
  • 따라서 감염 처리를 하는 배열을 따로 생성하고(≠visited), 감염되지 않은 칸만 세주었다.

코드

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	private static final int EMPTY = 0;
	private static final int VIRUS = 2;

	private static int N;
	private static int M;

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

	private static int[][] matrix;

	private static List<Point> points = new ArrayList<>();
	private static List<Point> viruses = new ArrayList<>();

	private static int safeArea = 0;

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

		String[] temp = br.readLine().split(" ");

		N = Integer.parseInt(temp[0]);
		M = Integer.parseInt(temp[1]);

		matrix = new int[N][M];

		StringTokenizer st;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < M; j++) {
				matrix[i][j] = Integer.parseInt(st.nextToken());

				if (matrix[i][j] == EMPTY) {
					points.add(new Point(j, i));
				}

				if (matrix[i][j] == VIRUS) {
					viruses.add(new Point(j, i));
				}
			}
		}

		combination(0, 0);

		System.out.print(safeArea);
	}

	private static void combination(int depth, int lastIndex) {
		if (depth == 3) {
			int[][] copied = new int[N][M];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					copied[i][j] = matrix[i][j];
				}
			}

			for (Point start : viruses) {
				BFS(start, copied);
			}

			int sum = 0;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (copied[i][j] == EMPTY)
						sum += 1;
				}
			}

			safeArea = Math.max(sum, safeArea);
			return;
		}

		for (int i = lastIndex; i < points.size(); i++) {
			Point p = points.get(i);
			matrix[p.y][p.x] = 1;
			combination(depth + 1, i + 1);
			matrix[p.y][p.x] = 0;
		}
	}

	private static void BFS(Point start, int[][] copied) {
		Queue<Point> queue = new ArrayDeque<>();

		queue.add(start);

		while (!queue.isEmpty()) {
			Point p = queue.poll();

			int nr = 0;
			int nc = 0;
			for (int i = 0; i < dr.length; i++) {
				nr = p.y + dr[i];
				nc = p.x + dc[i];

				if (!isValid(nr, nc)) {
					continue;
				}

				if (copied[nr][nc] == EMPTY) {
					copied[nr][nc] = VIRUS;
					queue.add(new Point(nc, nr));
				}
			}
		}

		return;
	}

	private static boolean isValid(int nr, int nc) {
		return (nr > -1 && nc > -1 && nr < N && nc < M);
	}

}

문제 풀이 날짜: 2023.09.18
포스트 작성일: 2023.09.30

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

문제 출처

백준 온라인 저지 1717번: 집합의 표현 (골드5)

키워드

유니온 파인드

풀이 접근법

• 유니온 파인드의 기초적인 구현을 묻는 문제이다.
• 합집합 연산은 union 함수, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 find 함수가 수행한다.
• 정확한 연산을 위해 트리의 깊이인 rank 배열을 선언한다.
  • 합집합 연산을 수행할 때마다 트리의 다음 레벨에 노드를 붙이게 되므로 rank를 증가시킨다.

코드

import java.io.*;

public class Main {
	
	private static int[] root;
	private static int[] rank; 

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] temp = br.readLine().split(" ");
		int n = Integer.parseInt(temp[0]);
		int m = Integer.parseInt(temp[1]); 
		
		root = new int[n + 1];
		rank = new int[n + 1];
		for(int i = 0; i <= n; i++) {
			root[i] = i;
			rank[i] = 0;
		}
		
		StringBuilder sb = new StringBuilder();
		for(int i = 0; i < m; i++) {
			temp = br.readLine().split(" ");
			
			int operation = Integer.parseInt(temp[0]);
			int a = Integer.parseInt(temp[1]);
			int b = Integer.parseInt(temp[2]);
			
			if(operation == 0) {
				union(a, b);
			}
			else if(operation == 1) {
				boolean result = isSameSet(a, b);
				
				if(result) {
					sb.append("YES").append('\n');
				}
				else {
					sb.append("NO").append('\n');
				}
			}
			else {
				continue;
			}
		}
		
		System.out.print(sb);
	}
	
	public static int find(int x) {
		if(root[x] == x) {
			return x;
		}
		else {
			return root[x] = find(root[x]);
		}
	}
	
	public static void union(int x, int y) {
		x = find(x); 
		y = find(y);
		
		if(x == y) {
			return;
		}
		
		if(rank[x] < rank[y]) {
			root[x] = y;
		}
		else if(rank[x] >= rank[y]) {
			root[y] = x;
		}
		
		if(rank[x] == rank[y]) {
			rank[x]++;
		}
	}
	
	public static boolean isSameSet(int x, int y) {
		x = find(x);
		y = find(y);

		return (x == y);
	}
}

git 링크

(git 링크 첨부)

문제 풀이 날짜: 2023.09.18
포스트 작성일: 2023.09.30

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

문제 출처

프로그래머스 : 입국심사 (Lv.3)

키워드

이분 탐색

풀이 접근법

• 이분탐색은 탐색 범위를 좁혀가면서 최댓값&최솟값 또는 근사치를 찾을 때에 유용하게 사용된다.
• “모든 사람이 심사를 받는 데 걸리는 시간의 최솟값”의 의미
  
  • 검사를 완료한 사람이 n명에 다다를 때까지 반복하고 그 lower bound를 구한다.
  • 누적 소요 시간이 k초일 때 이를 각 검색대 별 소요 시간으로 나누어보면 검사를 마친 인원 수가 계산된다.
  • 검사 완료된 인원수가 [n - 1, n - 1, n, n, n, n, n + 1, …] 이라면 n이 처음 출현한 시간을 구해야 함 ⇒ 이것이 최소 시간
  • 굳이 여러 구간을 동시에 탐색하지 않아도 현재까지의 경과 시간을 각 검색대별 시간으로 나눠보면 각 검색대별로 심사를 마친 인원을 모두 구할 수 있다.
  • 시간이 빠른 순서부터 검사를 받아보아야 하므로 입력 배열을 정렬한다.
•  이분탐색의 start와 end는 무엇으로 정의하는 게 좋은가?
  • 각 검색대 별로 가장 짧은 소요시간부터 (검색대의 최대 소모 시간 × 인원수)까지 탐색한다.
  • 탐색을 멈추는 key 값은 모든 검색대에서 심사를 마친 인원수이다. (key == n)
• 주어진 입력들의 합을 구하다보면 오버플로우가 날 위험이 있으므로 변수를 long타입으로 선언하여 푼다.

코드

import java.util.*;

class Solution {
    public long solution(int n, int[] times) {
        long answer = Long.MAX_VALUE;
        
        Arrays.sort(times);
        
        long start = times[0];
        long end = times[times.length - 1] * (long)n;
        
        while(start <= end) {
            //오버플로우 발생 가능(1)
            long mid = start + ((end - start) / 2);
            
            long sum = 0;
            for(int t : times) {
                long numOfPeople = mid / t; //오버플로우 발생 가능(2)
                sum += numOfPeople;
            }

            if(sum >= n) { //lower bound를 찾으며 범위를 좁힌다
                answer = Math.min(answer, mid);
                end = mid - 1;
            }
            else { //(sum < n)
                start = mid + 1;
            }
        }
        
        return answer;
    }
}

참고한 링크

https://suhyeokeee.tistory.com/183

문제 풀이 날짜: 2023.09.12
포스트 작성일: 2023.09.30

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

문제 출처

백준 온라인 저지 1062번: 가르침 (골드4)

키워드

순열, Next Permutation

풀이 접근법

• 모든 단어는 anta로 시작해서 tica로 끝나기 때문에 이 단어에 들어가있는 알파벳 다섯개 a, n, t, i, c 가 우선순위를 갖는다.
• 하지만 단순히 알파벳 출현 빈도수만을 체크한다면 아래와 같은 반례가 존재한다.
• 이 테케에서 첫 번째 단어 빼고 다른 단어에는 x가 들어가지 않는다.

8 25
antaxxxxxxxxxxxxxxxxxxxtica
antaabctica
antadeftica
antaghijtica
antaklmntica
antaopqrtica
antastuvtica
antawxyztica

//x를 제외한 나머지 알파벳을 학습해야 함.

• 이 상황에서 x의 빈도수가 가장 높다고 해도 다른 알파벳을 학습해야 최댓값을 구할 수 있다.
  • 따라서 a, n, t, i, c 다섯 개를 제외하고 어떤 알파벳을 학습해야 하는지를 조합으로 구한다.
  • 시간을 단축시키기 위하여 Next Permutation으로 풀이하였다.
• 조합을 구할 때는, 현재까지 출현한 알파벳을 집계해서 각각의 인덱스를 Map으로 만들어 주었다.
  • 인덱스를 참조할 때는 Map을 이용해 O(1) 시간만에 이 알파벳의 학습 여부를 판단할 수 있다.

코드

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

public class Main {

	private static int N;
	private static int K;
	private static int result = 0;

	private static int[] items;
	private static String[] words;
	private static Map<Character, Integer> indexes = new HashMap<>();
	private static Set<Character> set = new HashSet<>();

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

		String[] temp = br.readLine().split(" ");

		N = Integer.parseInt(temp[0]);
		K = Integer.parseInt(temp[1]);
		words = new String[N];

		K = K - 5;
		if (K < 0) { // a, n, t, i, c 을 모두 학습할 수 없다면
			System.out.print(0);
			return;
		}

		for (int i = 0; i < N; i++) {
			words[i] = br.readLine();
			
			for (int j = 4; j < words[i].length() - 4; j++) {
				char c = words[i].charAt(j);
				
				if (c == 'a' || c == 'n' || c == 't'
						|| c == 'i' || c == 'c') { // a, n, t, i, c 제외
					continue;
				}
				
				set.add(c);
			}
		}
		
		int idx = 0;
		for(Character c : set) {
			indexes.put(c, idx++);
		}

		items = new int['z' - 'a' + 1 - 5];

		for (int i = items.length - 1; i >= items.length - K; i--) {
			items[i] = 1; // 뽑아야 하는 수만큼 초기화 시킨다.
		}

		do {
			result = Math.max(countWords(), result);
		} while (np(items));

		System.out.println(result);
	}

	private static int countWords() {
		int count = 0;
		all : for(String word : words) {
			for (int i = 4; i < word.length() - 4; i++) {
				char c = word.charAt(i);
				
				if (c == 'a' || c == 'n' || c == 't'
						|| c == 'i' || c == 'c') { // a, n, t, i, c 제외
					continue;
				}

				if(items[indexes.get(c)] == 0) {
					continue all; //읽을 수 없는 단어
				}
			}
			count++;
		}
		
		return count;
	}

	private static boolean np(int[] count) {
		int swapIdx = -1;
		for (int i = 1; i < count.length; i++) {
			if (count[i - 1] < count[i])
				swapIdx = i - 1;
		}
		if (swapIdx == -1)
			return false;

		int largerIdx = -1;
		for (int j = 1; j < count.length; j++) {
			if (count[swapIdx] < count[j])
				largerIdx = j;
		}

		swap(count, swapIdx, largerIdx);

		int j = count.length - 1;
		for (int i = swapIdx + 1; i < j; i++) {
			swap(count, i, j);
			j--;
		}

		return true;
	}

	private static void swap(int[] count, int swapIdx, int largerIdx) {
		int temp = count[swapIdx];
		count[swapIdx] = count[largerIdx];
		count[largerIdx] = temp;
	}
}

Next Permutation을 사용했음에도 동일 자바 대비 실행 시간이 조금 느리게 나왔다. 알파벳의 학습 여부를 boolean으로 체크하고, recursion으로 답을 찾으면 오히려 더 빠를 수도 있는데, 아무래도 Next Permutation으로 조합을 계산하는 시간을 줄였어도 컬렉션을 참조하는 시간이 오래 걸리는 듯하다.

git 링크

(git 링크 첨부)

문제 풀이 날짜: 2023.09.08
포스트 작성일: 2023.09.11

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

문제 출처

백준 온라인 저지 11591번: Mootube (Silver) (골드5)

키워드

BFS, 최소 신장 트리

풀이 접근법

• 최소 신장 트리(Spanning Tree)를 구하는 문제이다. 구현은 인접 리스트 그래프와 BFS로 하였다.
• 우선 인접하지 않은 모든 두 정점의 usado를 구한다.
  • BFS로 모든 점을 방문하면서 currStart와 연결되지 않은 정점을 발견하면 무조건 min을 넣어준다.
  • v번 정점과 연결된 모든 정점 중 usado가 k 이하인 것의 수를 센다.
• 가지치기를 하지 않으면 시간 초과가 나기 쉬우므로 주의한다.
  • K 이상인 정점의 수는 BFS 안에서 센다. (밖에서 세면 O(N^2) 만큼 더 소모)
  • graph를 Node 타입으로 선언하고, 그 안에 usado를 함께 저장한다.
  • usado가 K 이상인 정점만 큐에 넣어서 가지치기를 한다. 우리는 usado가 K 이상인 영상의 수만 세면 되며, 서로 연결되지 않은 두 정점의 usado는 그곳까지 가는 경로 중 최소인 것으로 결정된다.
  • (문제 3번 테케 참고) 만약 usado가 3이상인 것들만 찾는다고 했을 때, usado가 2인 정점을 넣어봤자 큐에 연결되지 않은 두 정점의 경로도 2로 초기화 된다. 그렇다고 해도 정답으로 카운트가 되지 않는다. 따라서 제외 시킨다.

코드

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

public class Main {

	private static int K;
	private static int count = 0;
	
	private static List<Node>[] graph;
	private static boolean[] visited;

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

		String[] input = br.readLine().split(" ");

		int N = Integer.parseInt(input[0]);
		int Q = Integer.parseInt(input[1]);

		graph = new LinkedList[N + 1];
		for (int i = 1; i <= N; i++) {
			graph[i] = new LinkedList<>();
		}
		
		visited = new boolean[N + 1];
		
		StringTokenizer st;
		for (int i = 0; i < N - 1; i++) {
			st = new StringTokenizer(br.readLine());

			int p = Integer.parseInt(st.nextToken());
			int q = Integer.parseInt(st.nextToken());
			int r = Integer.parseInt(st.nextToken());

			graph[p].add(new Node(q, r));
			graph[q].add(new Node(p, r));
		}

		// 1.인접하지 않은 두 정점의 usado를 구한다.
		// 2.v번 간선과 연결된 모든 정점 중 usado가 k 이하인 것의 수를 센다.
		StringBuilder sb = new StringBuilder();
		for(int q = 0; q < Q; q++) { //O(N)
			st = new StringTokenizer(br.readLine());
			
			K = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			
			BFS(v); // O(V + E);
			
			sb.append(count).append("\n");
			
			count = 0;
			visited = new boolean[N + 1];
		}
		
		System.out.println(sb);
		
	}

	private static void BFS(int from) {
		Queue<Integer> queue = new ArrayDeque<>();
		
		queue.add(from);
		visited[from] = true;

		while (!queue.isEmpty()) {
			int v = queue.poll();
						
			for(Node u : graph[v]) {
				//가지치기 => 어떤 간선의 가중치가 K이상이어야만 큐에 넣는다.
				if(!visited[u.num] && u.usado >= K) {
					count++;

					visited[u.num] = true;
					queue.add(u.num);
				}
			}
		}
		
		return;
	}

}

class Node {
	int num; //연결된 노드
	int usado;
	
	public Node(int num, int usado) {
		this.num = num;
		this.usado = usado;
	}
}

git 링크

(git 링크 첨부)

문제 풀이 날짜: 2023.09.07
포스트 작성일: 2023.09.11

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

문제 출처

백준 온라인 저지 14499번: 주사위 굴리기 (골드4)

키워드

구현, 시뮬레이션

풀이 접근법

• 주사위를 굴렸을 때 다음 눈에 해당하는 좌표가 어디인지를 구하는 게 중요하며, 구현하기도 쉽지 않다. 배열 값은 물리적으로(?) 떨어져 있어도 실제 주사위 상으로는 이어져있기 때문이다.
• 여기서 주사위 배열을 1차원 배열로 선언하고, 각 방향으로 밀었을 때 숫자가 어떻게 변화하는 지를 switch문으로 대입해준다. 동, 서, 남, 북 4가지 방향으로 주사위를 밀었을 때 주사위의 어느 눈이 어느 위치로 옮겨가는 지만 지정해주면 된다. (경우의 수가 많지 않기 때문에 충분히 하드코딩을 시도해볼 수 있다.)
• 주의1 : 범위를 벗어나지 않고 굴릴 수 있는 경우에만 주사위 값을 옮겨주어야 하며, 그 때에만 출력을 진행해야 한다.
• 주의2 : 입력 표기가 (x, y)이지만 사실상 (row, col) 순서로 들어온다!!
  • 따라서 row에 x를, col에 y를 대입하거나 입력 순서를 반대를 받자.

코드

import java.awt.Point;
import java.io.*;
import java.util.*;

public class Main {

	private static final int UPPER = 3;
	private static final int LOWER = 6;
	
	private static int N;
	private static int M;
		
	private static int[] dice;
	private static int[][] map;
	
	private static int[] dr = {0, 0, -1, 1}; //동, 서, 북, 남
	private static int[] dc = {1, -1, 0, 0};
	
	private static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		int y = Integer.parseInt(st.nextToken());
		int x = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		map = new int[N][M];
		dice = new int[LOWER + 1]; //인덱스 0은 사용하지 않음, 처음엔 모두 0
		
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		//명령어 받기 
		int mapR = y;
		int mapC = x;
		st = new StringTokenizer(br.readLine(), " ");
		for(int i = 0; i < K; i++) {
			int dir = Integer.parseInt(st.nextToken());
			
			Point moved = moveDice(dir, mapR, mapC);
			if(moved != null) { //주사위를 굴렸다면 지도 좌표 갱신
				mapR = moved.y;
				mapC = moved.x;
			}
		}
		
		System.out.print(sb);
	}

	private static Point moveDice(int dir, int mapR, int mapC) {
		int nr = mapR + dr[dir - 1];
		int nc = mapC + dc[dir - 1];
		
		if(!isValid(nr, nc)) {
			return null;
		}
		
		//굴릴 수 있다면 주사위의 방향을 바꿔준다.
		int temp = dice[UPPER];
		
		switch(dir) {
		case 1:
			dice[3] = dice[4];
			dice[4] = dice[6];
			dice[6] = dice[2];
			dice[2] = temp;
			break;
		case 2:
			dice[3] = dice[2];
			dice[2] = dice[6];
			dice[6] = dice[4];
			dice[4] = temp;
			break;
		case 3:
			dice[3] = dice[5];
			dice[5] = dice[6];
			dice[6] = dice[1];
			dice[1] = temp;
			break;
		case 4:
			dice[3] = dice[1];
			dice[1] = dice[6];
			dice[6] = dice[5];
			dice[5] = temp;
			break;
		}
		
		if(map[nr][nc] == 0) {
			map[nr][nc] = dice[LOWER];
		} else {
			//0이 아닌 경우에는 칸에 쓰여 있는 수가 주사위의 바닥면으로 복사되며, 
			//칸에 쓰여 있는 수는 0이 된다.
			dice[LOWER] = map[nr][nc];
			map[nr][nc] = 0;
		}
		
		//주의: 굴릴 수 없다면 출력하지 않는다.
		sb.append(dice[UPPER]).append("\n");

		return new Point(nc, nr);
	}

	private static boolean isValid(int r, int c) {
		return (r > -1 && c > -1 && r < N && c < M);
	}
}

참고한 링크

https://loosie.tistory.com/763
https://developer-ellen.tistory.com/118

문제 풀이 날짜: 2023.09.05
포스트 작성일: 2023.09.11

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

문제 출처

백준 온라인 저지 2613번: 숫자구슬 (골드2)

키워드

이분 탐색, 매개변수 탐색

풀이 접근법

• 이 문제에서 이분 탐색으로 구하는 대상은 각 구슬의 경계를 나누는 경계값이 아니라 구슬의 합이다.
  • left는 전체 구슬 중 가장 큰 값 한 가지(원소가 1개인 집합)이다.
  • right는 전체 구슬의 합(모든 원소를 포함한 집합)이다.
  • 형성해야 하는 그룹의 수와 현재까지 형성된 그룹의 수를 비교해가며 이분탐색 범위를 늘리거나 줄여간다.

코드

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

public class Main {

	private static int N;
	private static int M;

	private static int[] beads;
	
	private static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		beads = new int[N];

		int start = 0;
		int end = 0;
		st = new StringTokenizer(br.readLine(), " ");
		for(int i = 0; i < N; i++) {
			beads[i] = Integer.parseInt(st.nextToken());
						
			start = Math.max(beads[i], start);
			end += beads[i];
		}

		int answer = Integer.MAX_VALUE;
		
		int mid = 0;
		//parametric search
		while(start <= end) {
			mid = (start + end) / 2;
			
			if(isValidGroup(mid)) { //그룹의 수가 적다면
				end = mid - 1; //최댓값을 더 작게 잡는다.
				answer = Math.min(answer, mid);
			} else { //그룹의 수가 많다면
				start = mid + 1; //최댓값을 더 크게 잡는다.
			}
		}
		
		sb.append(answer).append("\n"); 
		
		printGroup(answer, M);
		
		System.out.println(sb);
	}

	private static void printGroup(int mid, int target) {
		int sum = 0;
		int count = 0;
		
		for(int i = 0; i < beads.length; i++) {
			sum += beads[i];
			
			if(sum > mid) {
				sum = beads[i]; //새로운 구간부터 다시 부분합을 구한다.
				//한 그룹을 모두 묶었으므로 append 해준다.
				sb.append(count).append(" ");
				
				target -= 1; //앞으로 뽑을 그룹 수 감소
				count = 0;
			}
			count += 1;
			
			//앞으로 구할 그룹의 수와 잔여 구슬의 수가 일치한다면 break
			if(N - i == target) break;
		}
		
		//다른 그룹을 모두 묶었는데 target이 0이 아니라면
		while(target-- > 0) { //1개짜리 그룹을 append 해준다.
			sb.append(count).append(" ");
			count = 1;
		}
	}

	private static boolean isValidGroup(int mid) {
		int sum = 0;
		int groupCount = 1;
		
		for(int i = 0; i < beads.length; i++) {
			sum += beads[i];
			
			if(sum > mid) {
				sum = beads[i]; //새로운 구간부터 다시 부분합을 구한다.
				groupCount++;
			}
		}
		
		return (M >= groupCount);
	}

}

매개변수 탐색은 아직 익숙하지 않았고, 각 구슬의 집합을 나누는 경계면을 골라야 한다고 생각했었기 때문에 풀이를 구상하기 어려웠다. 따라서 다른 분들의 풀이를 참고하였으며, 이분 탐색에서는 탐색의 대상을 올바르게 선정하는 것이 특히나 중요해보이므로 주의할 필요가 있겠다.

참고한 링크

https://zoosso.tistory.com/415
https://everenew.tistory.com/66