[JAVA] SWEA 7510 - 상원이의 연속 합

8984 단어 algorithmSWEASWEA

prefix sum을 계산해서 연속 합을 구하는식으로 짰다. 적절하게 break를 해주지 않으면 시간초과가 나온다.

import java.util.*;
class Solution
{
	public static void main(String args[]) throws Exception
	{
        Scanner sc = new Scanner(System.in);


        int T = sc.nextInt();

        StringBuffer sb = new StringBuffer();

        for (int tc = 1; tc <= T; tc++) {
            sb.append("#").append(tc).append(" ");

            int N = sc.nextInt();
            long count = 0;

            long sum[] = new long[N + 1];
            for (int i = 1; i <= N; i++) {
                sum[i] = sum[i - 1] + i;
            }
            for (int i = 1; i <= N; i++) {
                if (sum[i] == N)
                    count++;
                if(sum[i] < N)
                    continue;
                for (int j = i - 1; j >= 1; j--) {
                    if(sum[i] - sum[j] > N)
                        break;
                    if (sum[i] - sum[j] == N)
                        count++;
                }
            }

            sb.append(count).append("\n");

        }
        System.out.println(sb);

    }
}

좋은 웹페이지 즐겨찾기