(JAVA) 자바 16570번 : 앞뒤가 맞는 수열

 

 

https://www.acmicpc.net/problem/16570

 

16570번: 앞뒤가 맞는 수열

 

 

 

처음에 시행착오를 거치고 나서 정답을 도출했다.

 

 

바로.. 시간 초과!

 

 

제한 시간은 2초였기 때문에

 

for문 3개로는 버티질 못했던 것이다.

 

 

그래서 for문을 2개로 줄이는 방법이 없을까...?

 

무조건 있겠지...

 

이걸 찾는 것이 이 문제의 취지다!

 

 

 

라고 생각하여 골똘히 계속 생각했고,

 

 

해결 방법을 알아냈다!!!!

 

 

 

 

그래서 이번 포스팅 글은

 

매커니즘보단 해결 로직에 대해 설명하고 마칠 계획이다.

**** 이전 게시글들과 다름없이 소스코드는 맨 하단에 첨부했다. 참고바란다.

 

 

 

A1, A2, A3 ... Ak = An-k+1, An-k+2, ... An 인 수열을 앞뒤수열

이 때, k의 값 중 최댓값을 앞뒤계수

 

라고 한다.

 

 

 

 

이러한 앞뒤계수와 같은 방법의 개수를 구하는 법은

 

앞에서부터 비교하지말고

 

뒤에서부터 비교하자.

 

 

그 말은 뭐냐?

 

 

이 앞뒤수열의 핵심은 앞부분만 자를 수 있다는 것 이다.

 

 

 

a1, a2, ... ak 에서

 

a1, a2를 자르면

a3, a4, ... ak 가 되지만

 

이에 대응하는 수는

a1에서 시작하나 a3에서 시작하나 

 

가장 맨 끝에 맞춘 수가 된다.

 

 

즉, 

k = 5, n = 11 이라고 하자.

 

처음에 a1, a2, a3, a4, a5 <=> a7, a8, a9, a10, a11 를 비교한 후

 

특정 수(예를 들어, a1과 a2)를 자른 후에도 처음과 같이

a3, a4, a5, a6, a7 <=> a7, a8, a9, a10, a11 를 비교한다.

 

 

 

 

그렇기 때문에

 

for(int i = n - 1; i > 0; i--) {

   int j = n;

   int count = 0;

   while(num[i] 와 num[j] 가 다를 때 까지 반복) {

      count++;

      i와 j 1씩 감소 (같은 번째에 해당하는 두 수열의 원소는 같아야하므로)

   }

   sum[count]++;

}

 

와 같은 로직으로 해결할 수 있다.

 

*** 맨 끝에서 시작은 n으로 같다. (위 참고)

*** count : k의 값. 같은 수의 개수(수열)

*** sum[count] : 수열의 길이(k) 를 만들 수 있는 방법의 개수. 앞부분을 어떻게 자르느냐에 따라 여러가지 경우가 생길 수 있다.

 

 

 

 

머리로 이해한걸 말로 풀려니 어렵네요ㅠㅠㅠ

 

이해가 되지 않는 부분은 소스코드 및 주석을 참고해주시구

 

댓글 질문 받겠습니다!!

 

이글 보신 분들, 감사드리고 하루하루 행복하셨으면 좋겠습니다.

 

 

감사합니다.

 

 

소스코드

---