글 읽기 - 시간초과가 나는데 이유를 모르겠습니다.

keepyourweaponaimed 4년 전 0

1. 문제를 충분히 숙지했고

2. 다른 질답을 모두 읽었으며

3. 3번의 시도 끝에, 1) 시간초과 2) 틀림 3)틀림 의 결과를 얻었습니다.

시간초과 해결을 위해서 sqrt를 넣었으나 틀렸고

sqrt만 넣고 했는데 10, 2 의 케이스에 안되서 sqrt에다가 +1 해줬는데 틀렸습니다.

EU를 모르겠습니다..

hoxy 떠오르는 반례 있으신가요?

#include<stdio.h>
#include<math.h>
int main(){
  int a, b, tmp, flag = 0;
  scanf("%d %d", &a, &b);
  if(b > a){
    tmp = a;
    a = b;
    b = tmp;
    flag = 1;
  }
  for(int i=1; i<=sqrt(a+b)+1; i++){
    for(int j=sqrt(a+b)+1; j>=1; j--){
      if((a+b) == i * j){
        if((i-2) * (j-2) == b){
          if(flag == 1 && i < j)
            printf("%d %d\n", i, j);
          else if(i >= j)
            printf("%d %d\n", i, j);
        }
      }
    }
  }
}

lokilo 4년 전 0

자세한 내용은 생략하고 간단하게 화두를 던져드리자면

1) 처음에 왜 두 숫자를 바꾸는지에 대해서는 좀 의아합니다.

2) for문의 i와 j가 돌아가는 범위를 좀 생각해보실 필요성이 있을 것 같습니다.
-> 반례를 요청하셨기에 포함시켜드리자면...
24 9 의 경우는 위 프로그램에서 해를 구할 수 없습니다. 이유는 2)에 적힌 내용과 함께 생각해보시길 바랍니다.

sait2000 4년 전 0

j가 문제입니다 하나가 제곱근보다 작으면 다른 하나는 제곱근보다 커야죠.

in:
2608 1301

out:
1303 3

keepyourweaponaimed 4년 전 0

이렇게 수정했는데도 틀렸다고 나옵니다.

앞에 if문을 둔 이유는, 둘 중에 뭐가 더 큰지 선별하기 위해서 놓은 겁니다.

어떤게 가로이고 어떤게 세로인지 판별하기 위해서 flag를 둔거고,

flag가 나오면 세로가 더 큰거라고 볼 수 있습니다.

#include<stdio.h>
#include<math.h>
int main(){
  int a, b, tmp, flag = 0;
  scanf("%d %d", &a, &b);
  if(b > a){
    tmp = a;
    a = b;
    b = tmp;
    flag = 1;
  }
  for(int i=1; i<=a; i++){
    if((a+b) % i != 0) continue;
    for(int j=a; j>=1; j--){
      if((a+b) == i * j){
        if((i-2) * (j-2) == b){
          if(flag == 1 && i < j)
            printf("%d %d\n", i, j);
          else if(i >= j && flag == 0)
            printf("%d %d\n", i, j);
        }
      }
    }
  }
}

lokilo 4년 전 0

맨 앞의 if문은 빨간색 타일과 갈색 타일의 갯수를 바꾸는 결과를 초래할 것으로 생각됩니다.

그랬을 때 아랫쪽 if문에서는 빨간색 타일을 안으로 넣는 경우로 체크하게 될 것 같구요.

79brue 4년 전 1

추가로, 수학적으로 고민해 보신다면 반복문이 필요 없음을 알 수 있습니다.

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

문제

문제

출처

ICPC

시간초과가 나는데 이유를 모르겠습니다.

keepyourweaponaimed 4년 전 0

lokilo 4년 전 0

sait2000 4년 전 0

keepyourweaponaimed 4년 전 0

lokilo 4년 전 0

79brue 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말