문제링크 : https://www.acmicpc.net/problem/2023


아이디어

  • N자리가 주어졌을때 모든자리 순회 > 1e9 > 시간초과
  • 1의자리부터 소수일경우 넘어가고 넘어가는 순으로 하면어떨까
    • 그럼 BFS로 1의자리부터 N의자리까지 숫자 넣어서 체크해보자
      • 이때 BFS이니까 중복체크 필요
      • But, 큐 사용할경우 메모리 초과
        • dfs로 해결
  • 에라토스테네스의 채 사용시 > 메모리 초과
    • 소수 확인 메소드로 사용

시간복잡도 계산

  • DFS 시복도 : O(V+E) : 1e9
  • 근데 1의 자리에서 4개밖에 없으니까 DFS 가능할듯

인트 계산

  • 최대 8자리이므로, 인트 가능

코드

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
44
45
46
47
#include <iostream>
#include <queue>
#include <string>
#include <cmath>
using namespace std;
 
bool decimalChk(int num) {
    // sqrt 까지 확인하면됨
    for(int i=2; i<=sqrt(num); i++) {
        if(num%i == 0) {
            return false;
        }
    }
    return true;
}
int N;
void dfs(int num) {
    if(to_string(num).size() == N) {
        cout << num << '\n';
        return;
    }
    
    for(int i=0; i<=9; i++) {
        string es = to_string(num) + to_string(i);
        int ei = stoi(es);
        if(decimalChk(ei) == 1) {
            dfs(ei);
        }
    }
}
 
 
int main() {
 
    cin >> N;
    
    for(int i=2; i<10; i++) {
        
        if(decimalChk(i) == 1) {
            dfs(i);
        }
    }
    
 
    return 0;
}
 
cs

문제유형

  • 그래프 탐색(BFS + DFS)

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

백준 1965 상자넣기 쉬운 풀이 (C++/CPP)  (0) 2021.02.21
백준 1715 카드 정렬하기  (0) 2021.02.21
백준 1248 맞춰봐 쉬운 풀이 (C++/CPP)  (0) 2021.02.21
백준 2169 로봇 조종하기 쉬운 풀이 (C++/CPP)  (0) 2021.02.21
백준 2467 용액 쉬운 풀이 (C++/CPP)  (0) 2021.02.17

문제링크 : https://www.acmicpc.net/problem/1248


문제 추상화

  • 숫자 갯수와, 각 구간합이 주어졌을때, 각 숫자 구하기

아이디어

  • 백트래킹으로 일일히 구하는 것이 가능할까?

    • A는 -10~10 > 21개
    • 21 ^ 10 가 일치해야함 > 너무큼
    • 다른방법이 있나?
      • 가지치기로 백트래킹 시간복잡도가 줄어들것 같긴한데...
      • 일단 해보자

시간복잡도 계산

  • 21^10

인트 계산

  • 숫자 범위 정해져있음 > INT 가능

코드

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <string>
#include <vector>
#include <numeric>
 
using namespace std;
 
vector<int> v;
int N;
string s;
char ec[15][15];
 
bool chk() {
    int cnt=0;
    for(int j=0; j<v.size(); j++) {
        for(int i=j; i<v.size(); i++) {
//            int idx = N * j + i;
            int sumv = accumulate(v.begin()+j , v.begin()+i+1,0);
            if(ec[j][i] == '-') {
                if( sumv>=0) return false;
            }else if(ec[j][i] == '0') {
                if(sumv !=0)return false;
            } else {
                if(sumv <= 0) return false;;
            }
            cnt++;
        }
    }
    
    return true;
}
 
void dfs() {
    if(v.size() == N) {
        for(int x : v) {
            cout << x << ' ';
        }
        exit(0);
        return;
    }
    
    // 전에 합한 수에따라 값을 올려줘서 시작
    
    
    for(int i=-10; i<=10; i++) {
        v.push_back(i);
        if(chk()==1) dfs();
        v.pop_back();
    }
}
 
int main() {
    cin >> N >> s;
    int cnt=0;
    for(int j=0; j<N; j++) {
        for(int i=j; i<N; i++) {
            ec[j][i] = s[cnt++];
        }
    }
    
    dfs();
    
    
    return 0;
}
 
 
cs

문제유형

  • 백트래킹

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

백준 1715 카드 정렬하기  (0) 2021.02.21
백준 2023 신기한 소수 쉬운 풀이 (C++/CPP)  (0) 2021.02.21
백준 2169 로봇 조종하기 쉬운 풀이 (C++/CPP)  (0) 2021.02.21
백준 2467 용액 쉬운 풀이 (C++/CPP)  (0) 2021.02.17
백준 1915 가장 큰 정사각형 쉬운 풀이 (C++/CPP)  (0) 2021.02.17

문제링크 : https://www.acmicpc.net/problem/2169


아이디어

  • DP - DFS 방법으로, 끝에서부터 시작하여 거꾸로 시작점까지 오면 될것으로 예상

  • 그런데 왼쪽으로 이동할 수 있다는 것이 기존 문제 유형과 다른점

  • 왼쪽에서 이동할경우 무한루프가 발생할 수 있으니까, 이전 좌표를 인식하고, 해당 좌표 제외한것만 DP 하면 어떨까?

    • 이러면 무한루프 발생할 수 있음

  • DP에 각 방향을 정해서, 해당 방향에서 들어온 경우를 나눔

    • DP[y][x]에서 k 방향으로 들어온 경우, DP[y+dy[k]][x+dx[k]]방향에서는 k방향으로 들어온것 제외하고 계산
    • 마지막에 k값중 최대값을 답으로

  • 점화식

    • DP[y][x][k] = y, x 좌표에서 이전에 k방향에서 들어와서 탐사한 결과의 최대값
    • 예시 : DP[y][x][0] = DP[y+dy[k0]][x+dx[0]][0] + DP[y+dy[k0]][x+dx[0]][1]

시간복잡도 계산

  • 한 노드는 *3번
  • O(NN3) = 3e6 >> 가능

인트 계산

  • DP가 가질수 있는 최대값 : 1000 * 1000 * 100 = 1e8 >> INT 가능

코드

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
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
 
using namespace std;
 
int map[1010][1010];
int dp[1010][1010][3];
int chk[1010][1010];
 
const int inf = -1e9;
int dy[] = {-1,0,0};
int dx[] = {0,1,-1};
int N,M;
// pre 값이라면 제외
int get_dp(int y, int x, int pre) {
    // dp가 이미 결정된 값인지 확인하는 여부 >> 초기화를 -1e9로
    if(dp[y][x][pre] != inf) return dp[y][x][pre];
    int maxv = inf;
    for(int k=0; k<3; k++) {
        if(pre == 1) if(k==2) continue;
        if(pre == 2) if(k==1) continue;
        int py = y +dy[k];
        int px = x +dx[k];
        if(py>=0 && py<N && px>=0 && px < M) {
            maxv = max(maxv, get_dp(py, px,k) + map[y][x]);
        }
         
    }
 
    return dp[y][x][pre] = maxv;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    fill(&dp[0][0][0], &dp[1009][1009][3], inf);
    fill(&chk[0][0], &chk[1009][1010], false);
    
    cin >> N >> M;
    for(int j=0; j<N; j++) {
        for(int i=0; i<M; i++) {
            cin >> map[j][i];
        }
    }
    for(int k=0; k<3; k++) {
        dp[0][0][k] = map[0][0];
    }
    
    
    cout << max(max(get_dp(N-1,M-1,0), get_dp(N-1,M-1,1)), get_dp(N-1,M-1,2)) << '\n';
    
    
    return 0;
}
 
cs

문제유형

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

백준 2023 신기한 소수 쉬운 풀이 (C++/CPP)  (0) 2021.02.21
백준 1248 맞춰봐 쉬운 풀이 (C++/CPP)  (0) 2021.02.21
백준 2467 용액 쉬운 풀이 (C++/CPP)  (0) 2021.02.17
백준 1915 가장 큰 정사각형 쉬운 풀이 (C++/CPP)  (0) 2021.02.17
백준 1339 단어수학 쉬운 풀이 (C++/CPP)  (0) 2021.02.16

+ Recent posts

티스토리툴바