-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
최대부분증가수열(LIS) 오답 질문
24.06.21 14:06 작성 조회수 47
0
이번 강의 코드와 100% 유사한 백준 문제가 있어서 풀었는데 98%에서 오답처리 되었습니다.
강사님의 강의를 이해하고 풀다보니 강의와 코드가 똑같은데 왜 오답이 나오는건가요??
https://www.acmicpc.net/problem/11053
제 코드는 이렇습니다.
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr= new int[n];
for(int i=0; i<n; i++) arr[i] = sc.nextInt();
int[] dp= new int[n];
int answer=0;
dp[0]=1;
//solve
for(int i=1; i<n; i++){
int tmp=0;
for(int j=i-1; j>=0; j--){
if(arr[i] > arr[j]) tmp=Math.max(tmp, dp[j]);
}
dp[i]=tmp+1;
answer=Math.max(answer,dp[i]);
}
System.out.println(answer);
}
}
답변을 작성해보세요.
0
인프런 AI 인턴
2024.06.21
안녕하세요, 인프런 AI 인턴입니다.
질문자님의 상황에 대해 답변을 드리기 전에, 유사한 상황에서의 질문과 그에 대한 해결 방안을 포함한 지식 공유자의 답변을 찾아보았습니다.
허정현님의 질문에 가장 밀접하게 연관된 내용은 “증가하는 수열 응용문제”에 대한 지식공유자 김태원님의 답변입니다. 이 답변에서는 증가하는 수열(LIS) 문제를 더 깊게 다루며, 영상 강의에서 학습한 내용을 바탕으로 한 응용 문제를 풀이하는 데 있어 유용한 조언이 포함되어 있습니다. 특히 백준 문제(#14002)에 대한 해결 과정을 제시하며, 해당 문제는 증가하는 수열의 길이뿐만 아니라 순열까지 나타내는 것이 포함되어 있어, 질문자님이 참고하신 백준 문제(#11053)와 관련이 깊습니다.
질문자님의 코드와 비슷한 부분이 있음에도 오답 처리가 되는 상황에 대해서는, 다음의 링크를 참조해주세요.
- 증가하는 수열 응용문제
이 답변에서 지식공유자 김태원님은 복잡한 코드를 좀 더 간소화하여 피드백을 제공하셨습니다. 비록 직접적인 문제(#11053) 해결에 관한 내용은 아니지만, LIS 문제를 해결하는 데 있어서 기본적인 접근 방식과 응용력을 향상시키는 데 매우 도움이 될 것입니다.
질문자님의 문제와 직접적으로 관련된 구체적인 오류를 찾기 위해선, 제공된 코드의 작은 논리적 차이나 백준 문제의 특정 테스트 케이스가 문제 코드와 어떻게 맞지 않을 수 있는지를 꼼꼼히 확인하는 것이 필요합니다. 때로는 초기화 방식, 경계 조건 검사, 혹은 알고리즘의 효율성 면에서 문제가 발생할 수 있습니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
답변 1