BOJ : https://www.acmicpc.net/problem/1149

github : https://github.com/junho0956/Algorithm/blob/master/1149/1149/%EC%86%8C%EC%8A%A4.cpp

 

재귀를 통해서 RGB거리에 대한 최소합을 구현하였습니다.

범위를 벗어나면 dp의 최소값을 계속 적용시켜주기 위해 maxi를 반환하였고

범위내에 포함만 된다면 dp값을 계속 확인해가면서 칠할 수 있는 최소값을 저장해두었습니다.

 

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 <iostream>
#include <algorithm>
using namespace std;
 
#define maxi 987654321
int dp[1000][3];
int arr[1000][3];
int n;
 
int dfs(int house, int color) {
    if (color < 0 || color > 2) return maxi;
    if (house == n - 1) return arr[house][color];
 
    int& res = dp[house][color];
    if (res) return res;
 
    res = maxi+10000;
 
    for (int i = 0; i < 3; i++) {
        if (i != color) res = min(res, dfs(house + 1, i));
    }
    res += arr[house][color];
 
    return res;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    cin >> n;
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < 3; j++)
            cin >> arr[i][j];
 
    int ans = 987654321;
    for (int i = 0; i < 3; i++) {
        ans = min(ans, dfs(0, i));
    }
 
    cout << ans;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 10995번 별 찍기 - 20  (0) 2020.02.21
BOJ 11654번 아스키 코드  (0) 2020.02.21
BOJ 2941번 크로아티아 알파벳  (0) 2020.02.21
BOJ 15993번 1, 2, 3 더하기 8  (0) 2020.02.20
BOJ 15992번 1, 2, 3 더하기 7  (0) 2020.02.19

BOJ : https://www.acmicpc.net/problem/2941

github : https://github.com/junho0956/Algorithm/blob/master/2941/2941/%EC%86%8C%EC%8A%A4.cpp

 

문제에서 요구하는 조건 그대로 구현하시면 쉽게 해결됩니다

 

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
#include <iostream>
#include <string>
using namespace std;
 
int main() {
    string str;
    cin >> str;
    str += "          ";
    int cnt = 0;
    for (int i = 0; i < str.size()-10; i++) {
        if (str[i] == 'l') {
            if (str[i + 1] == 'j') cnt++, i++;
            else cnt++;
        }
        else if (str[i] == 'c') {
            if (str[i + 1] == '=' || str[i + 1] == '-') cnt++, i++;
            else cnt++;
        }
        else if (str[i] == 'd') {
            if (str[i + 1] == 'z' && str[i + 2] == '=') cnt++, i += 2;
            else if (str[i + 1] == '-') cnt++, i++;
            else cnt++;
        }
        else if (str[i] == 'n') {
            if (str[i + 1] == 'j') cnt++, i++;
            else cnt++;
        }
        else if (str[i] == 's') {
            if (str[i + 1] == '=') cnt++, i++;
            else cnt++;
        }
        else if (str[i] == 'z') {
            if (str[i + 1] == '=') cnt++, i++;
            else cnt++;
        }
        else cnt++;
    }
 
    cout << cnt;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 11654번 아스키 코드  (0) 2020.02.21
BOJ 1149번 RGB거리  (0) 2020.02.21
BOJ 15993번 1, 2, 3 더하기 8  (0) 2020.02.20
BOJ 15992번 1, 2, 3 더하기 7  (0) 2020.02.19
BOJ 15991번 1, 2, 3 더하기 6  (0) 2020.02.18

BOJ : https://www.acmicpc.net/problem/15993

github : https://github.com/junho0956/Algorithm/blob/master/15993/15993/%EC%86%8C%EC%8A%A4.cpp

 

오랫동안 고민했는데 못풀었습니다.

딱히 규칙이 눈에 보이지 않았고 재귀로 짜볼려니 구현하다가 막히고 ㅠ

 

(emoney96 친구가 문제를 보자말자 해결해줬습니다. 존경하는 그저 갓.. )

 

점화식 dp[num] 은 홀수기준 짝수dp의 -1, -2, -3 을 모두 더한 값, 짝수기준 홀수dp의 -1,-2,-3 을 모두 더한 값 입니다.

왜 저는 이런 규칙이 안보이는건지 씁쓸합니다.. 다시 한번 갓 emoney96..

이렇게 해서 1,2,3 더하기 시리즈 해결했네요!

 

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
#include <iostream>
typedef long long ll;
using namespace std;
 
ll odd[100001];
ll even[100001];
const int mod = 1e9 + 9;
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    odd[1] = 1, odd[2] = 1, odd[3] = 2;
    even[1] = 0, even[2] = 1, even[3] = 2;
 
    for (int i = 4; i <= 100000; i++)
        odd[i] = (even[i - 1] + even[i - 2] + even[i - 3])%mod, even[i] = (odd[i - 1] + odd[i - 2] + odd[i - 3])%mod;
 
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        cout << odd[n] << " " << even[n] << "\n";
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 1149번 RGB거리  (0) 2020.02.21
BOJ 2941번 크로아티아 알파벳  (0) 2020.02.21
BOJ 15992번 1, 2, 3 더하기 7  (0) 2020.02.19
BOJ 15991번 1, 2, 3 더하기 6  (0) 2020.02.18
BOJ 15990번 1, 2, 3 더하기 5  (0) 2020.02.18

BOJ : https://www.acmicpc.net/problem/15992

github : https://github.com/junho0956/Algorithm/blob/master/15992/15992/%EC%86%8C%EC%8A%A4.cpp

 

아!! 시간초과 때문에 되게 힘들었는데 깊은 깨달음 덕분에 문제를 해결할 수 있었습니다!!

진짜 고민많이 했었는데 코드는 분명 정답을 출력하지만 시간초과를 해결할 수 없었습니다 ㅠㅠ..

 

깨닫게 된 것은 경우의 수가 0 이 될 수 있다는 것이였습니다.

항상 문제를 풀때 dp를 전역배열로 선언해두고 건드리지 않았었는데,

이렇게 되면 디폴트값인 0이 들어가게 됩니다.

저는 원하는 dp값을 찾아 들어가는 재귀가 dp가 0이 될 수 있는 경우임에도 불구하고 계속 재귀진입을 하게 되더라구요

dp를 -1 로 초기화해놓고 시작하니 빠르게 해결할 수 있었습니다.

별거 아니지만 저한테는 dp 초기화라는 것을 한번 생각하게끔하는 문제였습니다.

 

길이를 찾는 코드의 경우 딱히 어려운 부분은 없어서 읽어보시면 이해하실 것 같습니다.

점화식 dp[i][k] 의 의미는 "현재 길이가 k일 때 i를 만들 수 있는 경우의 수" 로 보시면 될 것 같습니다.

 

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
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
#define MOD 1000000009
 
ll dp[1001][1001];
 
ll dfs(int num, int cnt) {
    if (cnt < 0||num<0) return 0;
    
    if (num == 0) {
        if (cnt == 0) return 1;
        else return 0;
    }
 
    ll& res = dp[num][cnt];
    if (res != -1) return res;
 
    ll ans = 0;
    for (int i = 1; i <= 3; i++) {
        ans += dfs(num - i, cnt - 1) % MOD;
    }
    return res = ans%MOD;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    int T; cin >> T;
    memset(dp, -1, sizeof(dp));
    while (T--) {
        int num, m;
        cin >> num >> m;
        cout << dfs(num, m)%MOD << "\n";
    }
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 2941번 크로아티아 알파벳  (0) 2020.02.21
BOJ 15993번 1, 2, 3 더하기 8  (0) 2020.02.20
BOJ 15991번 1, 2, 3 더하기 6  (0) 2020.02.18
BOJ 15990번 1, 2, 3 더하기 5  (0) 2020.02.18
BOJ 15989번 1, 2, 3 더하기 4  (0) 2020.02.18

+ Recent posts

티스토리툴바