글 읽기 - 틀린 반례, 이유 찾아주세요

exon 2년 전 1

1. 틀린 이유, 반례 찾아주세요 (왜 틀렸는지 간단하게만)

2. 이 문제가 왜 DP 인지 간단하게 설명해주세요

감사합니다

#include <iostream>

int x[1001] = {0};
int dp[1001] = {0};

int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    int n = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &x[i]);
        dp[i] = 1;
    }
    int y = 1;
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            if (x[i] < x[j]) {
                x[i] = x[j];
                dp[i]++;
                y = max(dp[i], y);
            } 
        }
    }
    printf("%d", y);
}

dk10211 2년 전 3

1 4 2 3 5 6

dk10211 2년 전 1

21번째 줄에 값 바꿔버려서 그런 것 같네요

exon 2년 전 0

오!

제가 생각한거 보다 좀더 난이도있는 문제였네요.

O(N^3) 로 다시 코딩해야할거 같네요.

감사합니다!

dk10211 2년 전 0

dp로 푸시면 n^2에 가능해요 이분 탐색 활용하면 n log n

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

틀린 반례, 이유 찾아주세요

exon 2년 전 1

dk10211 2년 전 3

dk10211 2년 전 1

exon 2년 전 0

dk10211 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말