백준 1402번 아무래도이문제는A번난이도인것같다

드디어 중간고사가 끝났습니다. 사실 중간고사 공부를 하면서 꾸준히 코딩도 했어야했지만 제 역량이 부족해서.. ㅠㅠ

아무튼 문제 링크입니다: https://www.acmicpc.net/problem/1402

처음 문제를 풀 때는 모든 경우의 수를 다 구해보는 어리석은 판단을 했습니다. 당연히 TLE가 떴고 곰곰히 생각한 결과 모든 A는 A''를 만들 수 있다는 것을 깨달았습니다. 왜냐하면 A=A*1*1*1*1*1*...*1 이런식으로 필요한만큼 1을 곱할 수 있기 때문입니다.

#include <iostream>

using namespace std;

//결국 A=A*1*1*1*1*1*....*1*1 이런식으로 만들 수 있기 때문에

//모든 A는 A''를 만들 수 있다.

int main(void)

{

        int test_case;

        cin >> test_case;

 

        for (int i = 0; i < test_case; i++)

        {

                 int multiple, add;

                 cin >> multiple >> add;

                 cout << "yes" << endl;

        }

}

밑에는 제가 어리석게도 모든 경우의 수를 구하기 위해 시도했던 코드였습니다. 시간 제한이 없을 경우에도 AC가 나는지 궁금하지만 너무 많은 경우의 수가 있기 때문에 맞게 설계했는지 모르겠습니다.

#include <iostream>

#include <cmath>

using namespace std;

 

/*

void canMake(int multiple, int add)

{

        for (int i = 1; i <= sqrt(abs(multiple)); i++)

        {

                 int multiplicand = i;

                 int multiplier = multiple / i;

                 if (multiple > 0)

                 {

                         int possible[2] = { multiplicand + multiplier, -multiplicand - multiplier };

                         for (int j = 0; j < 2; j++)

                         {

                                 for (int k = 1; k <= sqrt(abs(possible[j])); k++)

                                 {

                                          int multiplicand2 = k;

                                          int multiplier2 = possible[j] / k;

                                          if (multiplicand2 + multiplier2 == add)

                                          {

                                                  cout << "yes" << endl;

                                                  return;

                                          }

                                          else if (-multiplicand - multiplier2 == add)

                                          {

                                                  cout << "yes" << endl;

                                                  return;

                                          }

                                 }

                         }

                 }

                 else

                 {

                         int possible[2] = { multiplicand - multiplier, -multiplicand + multiplier };

                         for (int j = 0; j < 2; j++)

                         {

                                 for (int k = 1; k <= sqrt(abs(possible[j])); k++)

                                 {

                                          int multiplicand2 = k;

                                          int multiplier2 = possible[j] / k;

                                          if (multiplicand2 + multiplier2 == add)

                                          {

                                                  cout << "yes" << endl;

                                                  return;

                                          }

                                          else if (-multiplicand - multiplier2 == add)

                                          {

                                                  cout << "yes" << endl;

                                                  return;

                                          }

                                 }

                         }

                 }

        }

        cout << "no" << endl;

}

 

int main(void)

{

        int test_case;

        cin >> test_case;

 

        for (int i = 0; i < test_case; i++)

        {

                 int multiple, add;

                 cin >> multiple >> add;

                 if (!multiple && !add)

                         cout << "yes" << endl;

                 else

                         canMake(multiple, add);

        }

        return 0;

}

*/

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~