글 읽기 - C++ 왜 시간초과가 나는지 모르겠습니다.

nyongja 4년 전 0

왜 시간초과가 나는 걸까요?ㅠㅠ

어디가 잘못된건지 잘 모르겠어요

#include <cstdio>

int main() {

	int caseNum;
	scanf("%d", &caseNum);

	while (caseNum--) {
		int num;
		int ans = 0;
		scanf("%d", &num);

		for (int l1 = 1; l1 <= 3; l1++) {
			if (l1 == num) ans++;
			for (int l2 = 1; l2 <= 3; l2++) {
				if (l1 + l2 == num) ans++;
				for (int l3 = 1; l3 <= 3; l3++) {
					if (l1 + l2 + l3 == num) ans++;
					for (int l4 = 1; l4 <= 3; l3++) {
						if (l1 + l2 + l3 + l4 == num) ans++;
						for (int l5 = 1; l5 <= 3; l3++) {
							if (l1 + l2 + l3 + l4 + l5 == num) ans++;
							for (int l6 = 1; l6 <= 3; l6++) {
								if (l1 + l2 + l3 + l4 + l5 + l6 == num) ans++;
								for (int l7 = 1; l7 <= 3; l7++) {
									if (l1 + l2 + l3 + l4 + l5 + l6 + l7 == num)ans++;
									for (int l8 = 1; l8 <= 3; l8++) {
										if (l1 + l2 + l3 + l4 + l5 + l6 + l7 + l8 == num)ans++;
										for (int l9 = 1; l9 <= 3; l9++) {
											if (l1 + l2 + l3 + l4 + l5 + l6 + l7 + l8 + l9 == num)ans++;
											for (int l10 = 1; l10 <= 3; l10++) {
												if (l1 + l2 + l3 + l4 + l5 + l6 + l7 + l8 + l9 + l10 == num)ans++;
											}
										}
									}
								}
							}
						}
					}
				}
			}

		}
		printf("%d\n", ans);

	}
	return 0;
}

nahwasa 4년 전 0

10중첩 반복문이시라니요.. 시간 복잡도가 ..!

일단 단순히 입력된 숫자 단 하나당 for문만 59000번 도는걸요?!

좀더 정확한 내용은 다음분이 해주실껍니다.

gojib2002 4년 전 0

입력으로 몇개가 들어올지 모르는데, 사실 n이 1~10밖에 안되니까 총 10번만 저 큰 반복문을 돌리시면 미리 다 구하실 수 있어요.

그걸 이용해서 입력 하나에 O(1) 처리가 가능하겠죠!

그리고 사실은 그 전처리를 하는데 저렇게 큰 반복문이 돌 필요가 없는데, 맨 앞 숫자가 1인 경우,2인 경우, 3인 경우 세가지가 있다는걸 생각해보시면 dp로 풀립니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

C++ 왜 시간초과가 나는지 모르겠습니다.

nyongja 4년 전 0

nahwasa 4년 전 0

gojib2002 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말