티스토리 뷰

알고리즘/BOJ

[백준] 9765 여섯 방정식

세진짱 2020. 3. 30. 22:49

 

참 어려워 보이는 문제다

근데 생각해보면 쉬운 문제다

물론 long long 안써서 처음에 틀렸다 ㅎㅎ

 

먼저 우리가 알아야할 x들은 소수라는 점을 기억하자

그럼 c1,c3,c5,c6은 소수 2개의 곱이므로 유일한 수 2개가 있을 것이다.

 

결국 완탐하면 된다!

이 문제에서 x4랑 x8은 의미없다 쓰지 않는다

 

완전탐색을 할 때

어떤 수 2개를 곱해서 c가 되야하므로 i*i<=c까지 보면 된다!

근데 이 때 x는 2 이상이므로 x와 c가 같다면 1,x가 나오므로 건너 뛰어야 한다

마지막으로 폭풍의 6중 for문으로 값을 확인해보자!

 

소수의 개념을 알면 쉽게 풀 수 있다!

그리고 범위 조심하자

 

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
ll c1,c2,c3,c4,c5,c6;
 
void solve(ll num,vector<ll> &vt1,vector<ll> &vt2){
    for(ll i=2;i*i<=num;i++){
        if(num!=&& num%i==0){
            vt1.push_back(i);
            vt1.push_back(num/i);
            vt2.push_back(i);
            vt2.push_back(num/i); 
            return;
        }
    }
}
int main(){
    cin>>c1>>c2>>c3>>c4>>c5>>c6;
    vector<ll> x1,x2,x3,x4,x5,x6,x7,x8;
 
    solve(c1,x1,x2);
    solve(c3,x6,x7);
    solve(c5,x2,x3);
    solve(c6,x6,x5);
 
    for(int a=0;a<x1.size();a++){
        for(int b=0;b<x2.size();b++){
            for(int c=0;c<x3.size();c++){
                for(int d=0;d<x5.size();d++){
                    for(int e=0;e<x6.size();e++){
                        for(int f=0;f<x7.size();f++){
                            if(x1[a]*x2[b]==c1 && x6[e]*x7[f]==c3 && x2[b]*x3[c]==c5 && x5[d]*x6[e]==c6){
                                printf("%lld %lld %lld %lld %lld %lld\n",x1[a],x2[b],x3[c],x5[d],x6[e],x7[f]);
                                return 0;
                            }
                        }
                    }
                }
            }
        }
    }
}
 
 

'알고리즘 > BOJ' 카테고리의 다른 글

[백준] 5214 환승  (0) 2020.03.31
[백준] 3088 화분 부수기  (0) 2020.03.30
[백준] 16932 모양 만들기  (0) 2020.03.06
[백준] 2580 스도쿠  (0) 2020.02.18
[백준] 3109 빵집  (0) 2020.02.14
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG
more
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함