랜선 자르기

실버2

랜선 자르기 JAVA 코드

문제 이해

• K개의 랜선을 잘라서 N개의 같은 길이의 랜선을 만든다
  • 1 <= K <= 10000
  • 1 <= N <= 1,000,000
  • K <= N
• N개의 같은 길이의 랜선을 만들 수 있는 최대 길이를 구하라

해결 방안

최소 길이는 1이고, 최대 길이는 랜선의 최대 길이다.

1부터 최대 길이까지 이분 탐색으로 현재 길이가 N개 이상의 랜선을 만들 수 있는지 확인하고, 그 최댓값을 출력하면 된다.

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

    int K = Integer.parseInt(st.nextToken());
    int N = Integer.parseInt(st.nextToken());

    long lines[] = new long[N];
    long start =1, end = 0;
    for (int i = 0; i < K; i++) {
        lines[i] = Long.parseLong(br.readLine());
        end = Math.max(end, lines[i]);
    }

    long ans = Long.MIN_VALUE;
    while (start <= end) {
        long mid= start + (end - start)/2;

        if (isSolution(lines, mid, N)) {
            start = mid + 1;
            ans = Math.max(mid, ans);
        } else {
            end = mid - 1;
        }
    }
    System.out.println(end);

}

private static boolean isSolution(long lines[], long target, int K) {
    int ans = 0;
    for (long line : lines) {
        ans += line / target;
    }
    return ans >= K;
}

오답노트

습관적으로 start을 0부터 시작해서 division by zero 에러가 발생했다

---

텀 프로젝트 [백준#9466]

골드3

텀 프로젝트 JAVA 코드

문제 이해

• 테스트케이스 T개가 주어진다
• 각 테스트케이스 당
  • 학생의 수 n명
    • 2<=n<=100,000
  • 각 학생은 팀하고 싶은 학생을 선택한다
    • 한 명만 선택
    • 자기 자신 선택 가능
• 팀의 조건: 다음 중 하나 충족
  • (1) 자기 자신을 선택하거나
  • (2) 사이클 형성
    • (예) 1이 2를 선택, 2가 3을 선택, 3이 1을 선택
• 어느 팀에도 속하지 않는 학생의 수를 구하라

해결 방안

• 방문 배열(boolean[])을 사용하여 학생의 방문 여부를 관리하고, 탐색 완료 배열(boolean[])을 사용하여 학생에 대한 탐색이 완료되었는지 관리한다

  • 탐색했어도, 완성되지 않았을 수 있다
  • 즉, 한 번의 dfs 메서드 호출 안에서 사이클을 찾으려면 한 개의 노드는 두 번 방문해야 하기 때문에 별도로 관리하는 것이다

• 아직 방문하지 않은 학생에 대해 DFS 탐색을 실시한다 visited[node] = true;

  • 현재 노드의 다음 노드는 이 학생이 팀하고 싶다고 선택한 학생
    • int next = students[node];
  • 다음 노드가 아직 방문되지 않았다면 dfs를 실시한다
  • 다음 노드를 방문했지만 아직 탐색이 완료되지 않았으면 사이클을 발견한 것 => 이 사이클의 멤버 수를 static 변수에 더한다

• DFS가 모두 완료되면 전체 학생 수에서 사이클에 포함되는 학생 수를 빼서 출력한다

---

N단 논법 [백준#15723]

실버1

N단논법 JAVA 코드

문제 이해

• n개의 전제와 m개의 결론이 주어진다
  • 2 <= n <= 26
  • 1 <= m <= 10
• 전제는 A is B의 형태로 주어진다
  • A is B면서 C is B일 수는 있지만, A is B면서 A is C일 수는 없다
• 전제에 기반해서 결론이 참인지 거짓인지 출력한다

해결 방안

• A is B에 대해 키 A에 값을 B를 갖는 HashMap<Character, Caharacter map을 저장한다
• 맵에 대해 DFS를 수행한다

---

어두운 굴다리 [백준#17266]

실버4

어두운 굴다리 JAVA 코드

문제 이해

• 굴다리의 길이 N이 주어진다
  • 1 <= N <= 100,000
• 굴다리에 M개의 가로등이 설치되어있고, 각 위치가 주어진다
  • 1 <= M <= N
• 가로등의 높이 H만큼 왼쪽으로 H, 오른쪽으로 H만큼 비춘다
• 가로등들이 굴다리 전체를 비추도록 하는 최소 높이를 구한다

해결 방안 (1)

그리디 풀이

가장 큰 가로등 간 거리를 구하고, 이를 2로 나눈 값

해결 방안 (2)

이진 탐색 풀이

이진탐색

1부터 N까지 이진탐색으로 굴다리 전체를 비출 수 있는 높이를 구한다

1. 굴다리 전체를 비출 수 있으면 최솟값을 구하기 위해 end = mid - 1
2. 굴다리 전체를 비추지 못하면 높이가 부족하다는 의미이기 때문에 start = mid + 1

while (start <= end) {
    int mid = start + (end - start)/2;
    boolean success = check(mid, N, locs);
    if (success) {
        ans = mid;
        end = mid - 1;
    } else {
        start = mid + 1;
    }

}

조건 충족 여부

조건 충족은 다음과 같이 확인한다

1. 0번째 가로등이 비추는 왼쪽 끝은 0 이하여야 한다
2. 마지막 가로등이 비추는 오른쪽 끝은 N 이상이어야 한다
3. i번째 (1이상) 가로등의 왼쪽끝은 (i-1)번째 가로등의 오른쪽 끝 이하여야 한다

---