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


아이디어

  • 백트래킹 - 조합 : 백트래킹 리스트 중 마지막것 다음부터 순회하며 백트래킹 수행

시간복잡도 계산

  • 10^N : 1e8 > 가능

자료구조

  • 백트래킹 리스트 : vector
    • 최대값 : 8이하의수 > INT 가능

코드(C++)

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
#include <iostream>
#include <vector>
 
using namespace std;
 
int N,M;
vector<int> v;
 
void dfs() {
    if(v.size() == M) {
        for(int x : v) cout << x << ' ';
        cout << '\n';
        return;
    }
    
    //리스트 중 마지막것 다음부터 순회하며 백트래킹 수행
    int last = 0;
    if(!v.empty()) last = v.back();
    
    for(int i=last+1; i<=N; i++) {
        v.push_back(i);
        dfs();
        v.pop_back();
    }
}
 
int main() {
    cin >> N >> M;
    dfs();
    return 0;
}
 
cs

문제유형

  • 백트래킹 - 순열, 조합
    • 순열 : 재귀함수 내에서 순회할때 이전 중복값 체크
    • 조합 : 리스트 마지막 다음부터 순회
    • 값 중복되지 않도록 : 재귀함수 내 before 사용해서, 이전이랑 값 같을경우 넘김

비슷한 문제

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

백준 15652 N과 M (4)  (0) 2021.03.15
백준 15651 N과 M (3)  (0) 2021.03.15
백준 15649 N과 M (1)  (0) 2021.03.15
백준 2579 계단 오르기  (0) 2021.03.14
백준 4179 불!  (0) 2021.03.14

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

아이디어

  • 백트래킹 - 순열
    • 이전값 중복체크만 해주면 됨

시간복잡도 계산

  • 백트래킹 : 10^N : 1e8 > 가능

자료구조

  • 백트래킹 vector

    • 최대 수 : 8이하 > INT 가능

코드(C++)

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
#include <iostream>
#include <vector>
 
using namespace std;
 
vector<int> v;
bool chk[10];
int N,M;
 
void dfs() {
    // 개수 가득 차면 출력
    if(v.size() == M) {
        for(int x : v) cout << x << ' ';
        cout << '\n';
        return;
    }
    
    for(int i=1; i<=N; i++) {
        if(chk[i]) continue;
        chk[i] = 1;
        v.push_back(i);
        
        dfs();
        
        chk[i] = 0;
        v.pop_back();
        
    }
}
 
int main() {
    fill(chk, chk+10, 0);
    cin >> N >> M;
    dfs();
    return 0;
}
 
cs

문제유형

  • 백트래킹 - 순열, 조합
    • 순열 : 재귀함수 내에서 순회할때 이전 중복값 체크
    • 조합 : 리스트 마지막 다음부터 순회
    • 값 중복되지 않도록 : 재귀함수 내 before 사용해서, 이전이랑 값 같을경우 넘김

비슷한 문제

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

백준 15651 N과 M (3)  (0) 2021.03.15
백준 15650 N과 M (2)  (0) 2021.03.15
백준 2579 계단 오르기  (0) 2021.03.14
백준 4179 불!  (0) 2021.03.14
백준 4485 녹색 옷 입은 애가 젤다지?  (0) 2021.03.14

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


아이디어

  • 이전에 계산한 값을 재활용 할 수 있음 > DP
    • 각 조건이 복잡하니까 2차원 DP로
    • DP[Y][X] : Y위치에서 X가 0이면, 이전에 한칸으로 온 경우, 1이면 이전에 2칸으로 온 경우
    • DP[Y][0] = DP[Y-1][1]
    • DP[Y][1] = max(DP[Y-2][0], DP[Y-2][1])
  • 초기값 설정
    • DP[1][0] = map[1]
    • DP[1][1] = 0
    • DP[2][0] = map[1] + map[2]
    • DP[2][1] = map[2];
      • DP[N][0], DP[N][1] 중 큰값 출력

시간복잡도 계산

  • O(N * 2)

자료구조

  • map[Y] : 계단 최대 1e4 > INT 가능
  • DP[Y][X] :
    • 최대값 : 1e4 * 300 = 3e6 > INT 가능

코드(C++)

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
#include <iostream>
 
using namespace std;
 
int map[310];
int dp[310][2];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    fill(&dp[0][0], &dp[309][2], 0);
    int N; cin >> N;
    for(int i=1; i<=N; i++) cin >> map[i];
    
    dp[1][0] = map[1];
    dp[1][1] = 0;
    
    dp[2][0] = map[1] + map[2];
    dp[2][1] = map[2];
    
    
    for(int i=3; i<=N; i++) {
        dp[i][0] = dp[i-1][1] + map[i];
        dp[i][1] = max(dp[i-2][0], dp[i-2][1]) + map[i];
    }
    
    cout << max(dp[N][0], dp[N][1]) << '\n';
    
    return 0;
}
 
cs

문제유형

  • 케이스 2차원 DP : 조건이 복잡할 때, 각 케이스에서의 dp

비슷한 문제

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

백준 15650 N과 M (2)  (0) 2021.03.15
백준 15649 N과 M (1)  (0) 2021.03.15
백준 4179 불!  (0) 2021.03.14
백준 4485 녹색 옷 입은 애가 젤다지?  (0) 2021.03.14
백준 1926 그림  (0) 2021.03.14

+ Recent posts

티스토리툴바