글 읽기 - 5615번 아파트 임대 시간초과가 나는데 반복문 조건을 어떻게 잡아야할까요?

degurii 6년 전 0

s = 2xy + x + y

s-x = 2xy +y

s-x = (2x+1)y

이므로

s-x%(2x+1) == 0 이라면 가능한 값이다

라는 아이디어로 풀었는데요

a%b 에서 a>=b 인데서 착안해

반복문 조건을 s-x>=2x+1로 잡았ㄴ는데

시간초과가 나네요

어떻게 해야 좋을까요?

#include <iostream>
using namespace std;

int cnt, n;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++){
		int s;
		cin >> s;
		bool c = false;
		for (int x = 1; s - x >= (2 * x + 1); x++){
			if ((s - x) % (2 * x + 1) == 0){
				c = true;
				break;
			}
		}
		if (!c) cnt++;
	}
	cout << cnt;
}

jh05013 6년 전 1

s가 2^31까지 가므로 x를 1부터 차례대로 돌려서는 풀 수 없습니다.

x를 차례대로 보지 않고 바로 푸는 방법이 있습니다.

degurii 6년 전 0

답변 감사합니다.

한번 생각해보겠습니다!

jh05013 6년 전 1

아 생각해 보니 바로는 아니네요... 그래도 훨씬 빠르게 끝낼 수 있습니다

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

문제

문제

출처

ICPC

5615번 아파트 임대 시간초과가 나는데 반복문 조건을 어떻게 잡아야할까요?

degurii 6년 전 0

jh05013 6년 전 1

degurii 6년 전 0

jh05013 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말