17611번 자바

2주만에 통과하는 알고리즘 코딩테스트 (2024년)

기억 ( 누적합 )

해결된 질문

작성

147

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] x = new int[1000001];
        int[] y = new int[1000001];

        // 첫 번째 꼭짓점
        int firstW = sc.nextInt() + 500000;
        int prevH = sc.nextInt() + 500000;
        int prevW = firstW;

        // 나머지 꼭짓점
        for (int i = 1; i < n; i++) {
            int w = sc.nextInt() + 500000;
            int h = sc.nextInt() + 500000;

            if (prevW == w) { // 수직선
                y[Math.min(prevH, h)]++;
                y[Math.max(prevH, h)]--;
            } else { // 수평선
                x[Math.min(prevW, w)]++;
                x[Math.max(prevW, w)]--;
            }

            prevW = w;
            prevH = h;
        }

        // 마지막 꼭짓점과 첫 번째 꼭짓점 연결
        if (prevW == firstW) { // 수직선
            y[Math.min(prevH, firstW)]++;
            y[Math.max(prevH, firstW)]--;
        } else { // 수평선
            x[Math.min(prevW, firstW)]++;
            x[Math.max(prevW, firstW)]--;
        }

        // 큰 값 찾기
        int xMax = 0;
        int yMax = 0;
        for (int i = 1; i < 1000001; i++) {
            x[i] += x[i - 1];   // 이전 값이랑 누적합
            y[i] += y[i - 1];
            xMax = Math.max(x[i], xMax);    // 큰 값 비교
            yMax = Math.max(y[i], yMax);
        }

        System.out.println(Math.max(xMax, yMax));
    }
}

안녕하세요 17611번 문제 자바로 풀고있습니다.

백준 게시판과 인터넷에 공유된 풀이가 거의 없어 커뮤니티에 질문 올리게 되었습니다.

문제에서 주어진 예를 테스트 했을 때는 잘 작동하는데, 제출시에(40%쯤) '틀렸습니다' 라고 나옵니다. 해당 코드로는 작동하지 않는 반례 또는 식의 오류를 알려주세요. 감사합니다.

python 코딩-테스트 알고리즘

답변 2

인프런 AI 인턴

안녕하세요, 인프런 AI 인턴입니다.

코드를 살펴보니 마지막 꼭짓점과 첫 번째 꼭짓점을 연결하는 부분에서 오류가 있는 것 같습니다. 현재 코드에서는 y[Math.min(prevH, firstW)]++;와 y[Math.max(prevH, firstW)]--;로 되어 있는데, 여기서 firstW가 아닌 firstH를 사용해야 하는 부분입니다. 변수 firstH는 선언되지 않았으므로, firstW와 같은 방식으로 첫 번째 꼭짓점의 높이를 저장하는 변수를 선언하고 사용해야 합니다.

올바른 접근은 다음과 같습니다:
- 첫 번째 꼭짓점의 높이를 저장할 int firstH = sc.nextInt() + 500000;를 추가하고,
- 마지막 꼭짓점과 첫 번째 꼭짓점을 연결할 때, firstH를 사용하여 수정합니다.

수정된 부분은 다음과 같습니다:

int firstH = sc.nextInt() + 500000; // 첫 번째 꼭짓점의 높이 저장 변수 선언 및 초깃값 설정
.
.
.
if (prevW == firstW) { // 수직선
    y[Math.min(prevH, firstH)]++;
    y[Math.max(prevH, firstH)]--;
} else { // 수평선
    x[Math.min(prevW, firstW)]++;
    x[Math.max(prevW, firstW)]--;
}

이러한 수정을 통해 첫 번째 꼭짓점과 마지막 꼭짓점을 올바르게 연결할 수 있고, 해당 문제에서 ‘틀렸습니다’ 오류를 해결할 수 있을 것입니다.

유미 이

질문자

위 상황으로 해결했습니다. 감사합니다.

코딩 센세

지식공유자

늦게 답변드려 죄송합니다..!! 이제 확인했네요.. 😢

질문 감사드립니다!

인프런 커뮤니티 질문&답변

17611번 자바