[ C++ ] Code-Up 1284: 암호 해독

 

안녕하세요? 수구리입니다.

 

C++ 책을 보며 공부를 하던 도중에

 

너무 책만 보니 따분하기도 하고,,

 

배우는 김에 C++에서 제공하는 다양한 기능들을 사용해보고,

 

간단하게 문제라도 풀어보는 게 좋을 것 같아서 알고리즘 문제들을 풀어보려고 합니다.

 

그래서 코드업 기본 예제들을 가지고 제가 풀었던 문제들 중에서 다룰만한 내용들을 복습할 겸 가지고 왔습니다!

 

 

 

[ 문제 ] 1284. 암호 해독

암호 해독

 

 

 

[ 나의 풀이 ]

#include <iostream>
using namespace std;

bool isPrime(int a){
    if (a == 2) return true; 	  // 2는 가장 작은 소수이므로 true 반환
    if (a % 2 == 0) return false; // 2로 나누어 떨어진다면 소수가 아니므로 false 반환
    
    // a를 반으로 줄여나가면서 나누어 떨어지는 수(i)가 있는지 판단 
    // -> 있다면 또다른 약수가 있으므로 a는 소수가 아님 false 반환
    for (int i = 3; i < a/2 ; i += 2){ 
        if ( a % i == 0 ) return false;
    }
    // -> 없다면 소수이므로 true 반환
    return true;
}
            
int main() {
    int n;
    bool flag = true;
    
    cin >> n;
    
    for (int i = 2; i < n; i++){

        if ( isPrime(i) ) {
            if ( isPrime(n / i) && (n % i == 0) && flag ) {
                cout << i << " " << (n / i) << endl;
                flag = false;
            } else if (!flag) {
                break;
            }
        }
    }
    if (flag) cout << "wrong number";
}

 

[ 설명 ]

1. 사용자로부터 어떤 수 n을 입력받는다.

2. 2부터 n까지 반복문을 수행하는데 i값은 isPrime이라는 함수를 거쳐 소수만 if 문을 통과하도록 한다.

3. 만약 n을 i로 나눈 수도 마찬가지로 소수이고, 나눈 나머지 값이 0이며 flag 값이 true 라면

4. 해당 i 값과 ( n / i ) 값을 출력해주고 flag를 false로 바꿔준다.

5. 그 후, else if 문에서 flag가 false이므로 !(not) 연산자를 통해 true로 바뀌고 break를 만나 for문 탈출

6. 만약, for 문을 다 돌았는데도 flag가 true라면, 두 소수의 곱으로 나타낼 수 없으므로 "wrong number 출력"