🤍 전 강의 25% 할인 중 🤍

2024년 상반기를 돌아보고 하반기에도 함께 성장해요!
인프런이 준비한 25% 할인 받으러 가기 >>

  • 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

5-H 질문

24.05.29 03:54 작성 24.05.29 04:37 수정 조회수 93

0

 http://boj.kr/f20dcd82536849b794b2b9f0551683f9

 

안녕하세요 큰돌님

이해가 안가는 부분이 있어서요

1 2 3 1 2

이렇게 있으면,

마지막 부분 3 1 2은 등차수열의 합을 이용한

(3) (1) (2) (3, 1) (1, 2) (3, 1, 2)

이렇게 경우의 수를 모두 세는데,

왜 1 2 3 같은 경우

(1) (1, 2) (1, 2, 3) 이런 경우만 고려하는 걸까요?

왜 (1) (2) (3) (1, 2) (2, 3) (1, 2, 3) 이렇게 세지 않는걸까요...

 

 

답변 2

·

답변을 작성해보세요.

1

안녕하세요 ㅎㅎ

로직상 그렇습니다.

이 문제의 풀이로직이 이렇게 나눠진다고 보시면 됩니다.

이 idx를 포함한 unique한 수열의 경우의 수 + 이 범위에서 unique한 수열의 경우의 수

 

이 idx를 포함한 unique한 수열의 경우의 수의 경우

a, b, c

라고 했을 때 a를 포함하는 unique한 수열의 경우의 수는

a

a b

a b c

이겠죠?

그리고 나서 idx를 오른쪽으로 움직여가면서 해당 로직을 반복하는 것이죠.

 

그러나 마지막에

이 범위에서 unique한 수열의 경우의 수의 수 같은 경우

a, b, c라고 했을 때

a

b

c

a, b

b, c

a, b, c

가 되기 때문입니다.



또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.


0

dudghk0924님의 프로필

dudghk0924

질문자

2024.05.30

설명해주신 답변에 대한 이해는 되었습니다..!

그런데 이 문제에서

이 idx를 포함한 unique한 수열의 경우의 수 + 이 범위에서 unique한 수열의 경우의 수

이렇게 나눠진 이유를 알 수 있을까요..?

왜 저렇게 나눠서 풀이를 하는지 이유를 알고 싶어요

안녕하세요 dudghk0924님 ㅎㅎ

일단 이 문제는 투포인터를 이용해서 배열 내의 모든 유일한 요소로 구성된 부분 배열을 찾아야 합니다.

왜 그런 생각이 나왔냐라는 것에 대한 플로우를 생각해보면...

이문제를 보시고 범위기반으로 유일한 요소로 구성됨 -> 범위? -> 투포인터로 범위를 정해서 해볼까? -> 투포인터로 풀 생각을 해야 함. -> 배열의 시작과 끝을 동시에 관리할 수 있어, 중복 요소를 빠르게 탐지하고 처리할 수 있기 때문이죠.

 

자 그러면 투포인터로 어떻게 풀어야할까? 까지 와야 합니다.

일단 e, s를 기반으로 지금의 범위를 만들고 -> (e - s)를 더해서 -> 현재 s에서 e까지의 모든 유일한 부분 배열에 대한 것을 고려할 수 있지 않을까? ->그러면서 .. e 포인터를 오른쪽으로 이동하며 새로운 요소를 추가하고 새 요소가 중복되지 않으면 계속 이동하고, 중복되면 s 포인터를 오른쪽으로 이동하여 중복 요소를 제거하는 식으로다가 해볼까?

 

근데? 마지막에 와서는 e - s를 더하면 될까? 어? 안되네? -> 아아.. 이 때는 (e - s) * (e - s + 1) / 2를 더해서 그 때의 모든 유일한 부분 배열을 한 번 더 계산해야 정답이구나

이래서 2개의 로직이 나오게 되는 것입니다.



또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.


채널톡 아이콘