인프런 커뮤니티 질문&답변
작성한 질문수
섹션 9 Dynamic Programming (동적 계획법) 최대부분증가수열
작성
·
31
·
수정됨
0
안녕하세요,
최대부분증가수열을 수강한 뒤에 백준에서 유사한 문제를 발견해서 풀었는데
https://www.acmicpc.net/problem/11053
강의에서 배운 그대로 해당 코드를 제출했더니 틀렸다는 답변을 받았습니다..
예제 입력은 맞게 나오는데 다른 테스트 케이스에서 틀린 것 같습니다..
해당 문제에서 놓친 부분이 있을까요..?
N = int(input())
arr = list(map(int, input().split()))
arr.insert(0,0)
dy = [0]*(N+1)
dy[1] = 1
res=0
for i in range(2, N+1):
max=0
for j in range(i-1, 0, -1):
if arr[i] > arr[j] and dy[j]>max:
max = dy[j]
dy[i] = max+1
if dy[i]>res:
res = dy[i]
print(res)
답변 2
0
안녕하세요^^
문제 조건을 보면
"첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다."
입력되는 수열의 길이가 1인 경우도 있습니다.
코드에서 res = 1 로 초기화하면 됩니다.
0
안녕하세요, 인프런 AI 인턴입니다. 김민경님,
최대 부분 증가 수열 문제는 종종 코드에서 초기화나 인덱싱 문제로 인해 틀린 결과를 받을 수 있습니다. 보내주신 코드를 바탕으로 몇 가지 사항을 점검해볼 수 있습니다.
- 초기화 문제: 시작 부분에서
dy[1] = 1로 초기화하셨는데, 아래와 같은 경우에는 모든 항목의 초기 값을 1로 설정하는 것이 더 일반적입니다. 이는 각 원소가 최소한 그 자체로 길이 1의 부분 수열을 형성하기 때문입니다.
dy = [1] * (N + 1) # dy[0]는 사용하지 않으므로, 편의상 dy를 N+1로 초기화했다면 처음부터 모두 1로 초기화
인덱싱: Python의 배열에서는 0부터 인덱스가 시작되어,
arr에 0을 추가하는 대신,dy와arr가 같은 크기 내부에서 동작하도록 맞추는 것이 중요합니다.중복된 변수 사용:
max라는 이름이 파이썬 내장 함수와 동일하므로 변수명으로 사용하지 않는 것이 좋습니다.max_length와 같은 명확한 이름을 사용해보십시오.
개선을 통해 문제를 해결해 보세요. 관련하여 유사한 문제 해결에 대한 참고를 위해, 다음의 답변들이 도움이 될 수 있을 것입니다:
- 증가하는 수열 응용문제에서는 매우 유사한 문제를 논의하고 있으니, 문제 해결 전략이나 코드 작성 방법을 참고하실 수 있습니다.
- DP에서 자신보다 아래 인덱스를 검사할 때 오름차순으로 해도 상관없나요?에서도 탐색 방향에 따른 구현 차이점과 파일을 검사할 때의 일반적인 원칙에 대해 다루고 있습니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.