인프런 커뮤니티 질문&답변
작성한 질문수
7-H 질문있습니다 :)
해결된 질문
작성
·
103
0
안녕하세요 선생님 🙂
한 가지 궁금한 것이 있어서 질문 드립니다 ^^
입력 값을 int형 변수가 아닌 vector컨테이너를 사용하면 문제가 생기는 경우가 있는데요, 무엇때문에 발생하는 문제인지 모르겠습니다.
아래는 정답의 수도코드입니다.
dp[0] = 1;
for (int i = 0; i < n; i++)
{
cin >> temp;
for (int j = temp; j <= k; j++)
{
dp[j] += dp[j - temp];
}
}여기서 안쪽 for문 중 j = 1로 변경하면, 연산 자체는 늘어나겠지만 정답인 것은 변함이 없습니다.
아래는 temp변수를 vector 컨테이너로 변경한 코드입니다.
vector<int> vec(n);
dp[0] = 1;
for (int i = 0; i < n; i++)
{
cin >> vec[i];
for (int j = vec[i]; j <= k; j++)
{
dp[j] += dp[j - vec[i]];
}
}temp 변수를 이용한 것보다 vector 컨테이너를 사용하기 때문에 공간복잡도와 시간복잡도 측면에서 손해를 보지만, 결과는 같습니다.
하지만, 안쪽 for문의 j를 j = 1로 수정하면 오답이 됩니다. 테스트케이스에서도 출력 값이 다르게 나오더라구요.
이유가 무엇인지 알려주시면 감사하겠습니다 :)
답변 2
1
안녕하세요 유태님 ㅎㅎ
안쪽 for문의 j를 j = 1로 수정하면 오답이 됩니다.
-> 입력값을 기반으로 시작해야 해서 그렇습니다.
cin >> temp;
for (int j = temp; j <= k; j++)앞의 코드처럼 입력을 받아서 해당 값부터 시작해야 하는데 1부터 시작해서 그렇습니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
0
안녕하세요, 인프런 AI 인턴입니다. 한유태님.
해당 문제는 DP(동적 프로그래밍)를 통해 특정 수를 만드는 데 필요한 경우의 수를 계산하는 문제로 보입니다. 여기서 핵심은 j의 시작점을 어디로 설정하냐인데, 이로 인해 결과가 달라질 수 있습니다.
주의해야 할 점
정답이 변하는 이유:
- 기본적으로
dp[j]는j를 만드는 방법의 수를 저장합니다.
j = vec[i]부터 시작하면 새로운 숫자를 추가하는 동안 해당 숫자보다 작은 경우의 수는 무시됩니다. 이는 특정 합을 만들 수 있는 방법을 정확하게 계산하기 위함입니다.
- 반면
j = 1부터 시작하면 불필요한 이전 값이 추가로 더해져 잘못된 결과를 도출할 수 있습니다. 이는 조합의 중복 발생의 위험이 있습니다.
- 기본적으로
vector<int> vec의 사용 차이:temp와vec[i]는 연산 자체엔 영향을 주지 않지만, 코드의 구조나 문제의 설정에 따라 작은 차이가 발생할 수 있습니다. 이는vec내의 값들이 어떻게 사용되느냐에 따라 영향이 달라질 수 있습니다.
결론
- 다이내믹 프로그래밍을 사용할 때는 작은 부분 문제의 해를 점차적으로 쌓아가면서 완전한 문제의 해를 얻는다는 원리를 항상 기억해야 합니다.
- 벡터와 같은 컨테이너를 사용할 때도 이 원칙이 동일하게 적용됩니다.
j = 1과j = vec[i]로 설정한 차이가 정확한 문제 해결을 위한 원리임을 명심하세요.
아래는 연관된 질문과 답변 링크입니다. 비슷한 문제 해결 방법에 대한 설명이 있습니다.
- 8 - I 코드내용 질문입니다! - 인덱스 처리와 범위에 대한 내용이 설명되어 있습니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.