[SWEA] 8840. 아바바바

문제

‘a’와 ‘b’가 번갈아 나오는 길이 L인 문자열이 있다. L = 5이면 “ababa”이고, L = 7이면 “abababa”이다.

홀수 L이 주어질 때, ‘a’와 ‘b’가 번갈아 나오는 길이 L인 문자열에서, 

길이가 2이상인 연속한 부분문자열이 회문(앞으로 읽어도 뒤로 읽어도 같은 문자열)인 것의 개수를 구하는 프로그램을 작성하라.

 

풀이방법

L이 최대 10^9까지 입력되므로 반복문을 사용할 경우 시간초과가 발생한다.

 

따라서 L이 입력되었을 때, 출력값을 바로 계산할 수 있는 규칙을 찾아야한다.

 

L=3이면 "aba"이고, 회문은 "aba" 하나를 만들 수 있다.

 

L=5이면 "ababa"이고, 회문은 "aba", "bab", "aba", "ababa" 3개를 만들 수 있다.

 

L=7이면 "abababa"이고, 회문은 "aba", "bab", "aba", "baba", "aba", "ababa", "babab", "ababa", "abababa" 7개를 만들 수 있다.

 

이러한 방식으로 L을 계속해서 늘려가며 규칙을 찾으면, 

 

L이 입력되었을 때 출력값은 {(L - 1) / 2 } ^ 2 이 된다.

 

소스코드

package samsung;

import java.util.*;

public class s_8840 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int tc = sc.nextInt();
		
		for(int t = 1; t <= tc; t++) {
			long n = sc.nextInt();
			long i = (n-1) / 2;
			System.out.println("#" + t + " " + (i*i));
		}
	}
}