글 읽기 - C언어로 도전중인데, 시간 초과 문제가 계속 뜹니다ㅠ

bfdcoco 1년 전 0

어쩌다보니 4중 for문을 사용하게 됐는데, 시간 초과가 계속 뜹니다. 혹시 문제점이 있다면 피드백 부탁드리고, 아니라면 해당 4중 for문을 대체할 방법에 대한 조언을 해주셨으면 합니다.

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

int main()
{	
	int repeat;
	int x1, y1, r1, x2, y2, r2;
	int List[999];
	int N = 0;

	scanf("%d", &repeat);

	for (int i = 0; i < repeat; i++) {

		int count = 0;
		scanf("%d %d %d %d %d %d", &x1, &y1, &r1, &x2, &y2, &r2 );

		for (int x = x1 - r1; x <= x1 + r1; x++) {
			for (int y = y1 - r1; y <= y1 + r1; y++) {
				for (int x_2 = x2 - r2; x_2 <= x2 + r2; x_2++) {
					for (int y_2 = y2 - r2; y_2 <= y2 + r2; y_2++) {

						if (x == x_2 && y == y_2 && ((x - x1) * (x - x1) + (y - y1) * (y - y1)) - r1 * r1 == 0 && ((x_2 - x2) * (x_2 - x2) + (y_2 - y2) * (y_2 - y2)) - r2 * r2 == 0) {
							count += 1;
							
						}

						else if (x1 == x2 && y1 == y2 && r1 == r2) {
							count = -1;
						}
					}
				}
			}
		}

		List[N] = count;
		N++;
	}

	for (int k = 0; k < repeat; k++) {
		printf("%d\n", List[k]);
	}

	return 0;
}

mk9901 1년 전 0

for 4문을 돌리면 수행 횟수가

20000 * 20000 * 20000 * 20000

= 160,000,000,000,000,000 (16경) 횟수를 돌게 됩니다.

차라리 수학식으로 정리해보시는 것이 어떨까요?

터렛위치 사이의 거리를 구하고

범위 안에 포함되는지 일치하는지 밖에 있는지 체크해보세요.

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

문제

문제

출처

ICPC

C언어로 도전중인데, 시간 초과 문제가 계속 뜹니다ㅠ

bfdcoco 1년 전 0

mk9901 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말