인프런 커뮤니티 질문&답변
작성한 질문수
5-h 반례를 못찾겠습니다!
해결된 질문
작성
·
26
0
안녕하십니까 큰돌 강사님
오늘도 질문 드립니다! 항상 감사합니다 ㅎㅎ
저의 구현 코드와 아이디어 첨부하겠습니다.
http://boj.kr/45f37e5b0999424ab3f1838167234492
테스트 케이스 바탕으로 설명하겠습니다
우선 제가 문제를 풀기위해 생각한 아이디어는
1 2 3 4 5 와 같은 수열이 있을 때 어디에 있는 수가 어디까지 영향을 미칠 수 있나를 생각했습니다.
제가 기준으로 세운 것은 특정 수가 본인과 앞에까지의 영향을 고려했습니다.
1인 상태에서 2가 들어오면 2가 영향을 줄 수 있는 수는 1과 본인으로 (1 2) (2) 이런 식의 경우의 수가 만들어집니다. 따라서 하나씩 수를 집어 넣고 그 수로 인해 만들어질 수 있는 경우의 수를 cnt했습니다.
5
1 2 3 1 21) (1)
2) (1 2) (2)
3) (1 2 3) (2 3) (3)
4) (1 2 3 4) (2 3 4) (3 4) (4)
5) (1 2 3 4 5) ( 2 3 4 5) (3 4 5) (4 5) (5)
이렇게 실제 15가지 경우의 수와 정답과 일치합니다
중복이 있는 경우를 예로 들겠습니다. 만약에 영향을 끼칠 수에 본인이 있다면 집어 넣지 않습니다.
5
1 2 3 1 21) (1)
2) (1 2) (2)
3) (1 2 3) (2 3) (3)
1) (2 3 1) (3 1) (1)
2) (3 1 2) (1 2) (2)
(1)처럼 묶음은 겹치나 생기는 위치가 달라서 cnt
이런식으로 12가지의 경우의 수와 정답과 일치합니다
이러한 로직을 코드로 구현했는데 정답이 아니여서 제 아이디어가 틀린건 지 제가 반례를 못잡은건지 궁금합니다.
오늘도 즐겁게 매웁니다. 가르쳐 주시면 감사하겠습니다!!
답변 2
0
0
안녕하세요, 인프런 AI 인턴입니다. Jh P님께서 제출하신 질문에 대한 답변을 준비했습니다.
질문하신 문제는 “반복되지 않는 부분 수열의 개수 구하기”라는 문제로 보입니다. 주어진 수열에서 모든 유일한 부분 수열을 찾는 것이 목표입니다. 각 숫자가 포함될 수 있는 모든 가능한 시작 지점에서의 부분 수열을 누적하여 개수를 구해야 합니다.
핵심 포인트: 모든 인덱스에서 시작하고 가능한 최대 유효한 부분 수열의 개수를 누적합니다. 그렇다면, 각 인덱스에서 시작하고 그 인덱스를 끝으로 지정할 수 있다면 그 범위까지 모든 유일한 조합을 고려해야 함을 기억하세요.
이미지로 이해를 돕기 위해 참고 자료도 추천드립니다:
BOJ 13144 문제 해설: 아마도 해당 문제에 대한 자세한 설명과 해설이 있습니다. 링크의 문제 설명을 참고하시면 대체로 로직의 조건들을 이해하는 데 도움이 될 것입니다.
예제 코드 및 문제 반례 예시: 예제 코드를 통해서 자신의 구현과 비교를 시도해 보세요. 가끔 직접 코드를 비교하면서 반례를 분석하는 것이 로직의 잘못된 부분을 찾는 데 도움이 될 수 있습니다.
해당 링크들을 통해서 자신이 작성한 로직을 점검해 보셔야 합니다. 특정한 수열에서의 부분 수열 처리에서 누락되거나, 초반 상태에서 초기화가 부정확한 경우가 주요 오류일 확률이 큽니다.
정확한 답에 도달하기 위해 다른 유사한 구현이나 해설을 참고하시고, 의도대로 작동되지 않은 케이스 및 오류를 발견했다면, 이러한 트러블슈팅 과정을 통해 수정해 보시기 바랍니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.