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

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

 

오르막수는 작아지는 부분이 없는 수를 말한다.

ex) 0000, 0001, 3333, 9999

 

*길이가 1 일때는 기본적으로 0-9 으로 시작하는 모든 수는 1가지의 경우만 가지게 된다.

*시작하는수가 9인 경우 가능한 수는 9999... 밖에 없으므로 1가지의 경우만 가지게 된다.

 

초기화 후 손으로 직접 값을 그려보면

dp[시작하는 수][길이] = dp[시작하는수][길이-1] + dp[시작하는수-1][길이] 라는 점화식을 유추해낼 수 있다.

 

더보기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
 
int dp[10][1001];
int N;
 
int main() {
    ios::sync_with_stdio(false);
 
    cin >> N;
    for (int i = 0; i < 10; i++) dp[i][1] = 1;
    for (int i = 2; i <= N; i++) dp[0][i] = 1;
     
    for (int k = 2; k <= N; k++)
        for (int i = 1; i < 10; i++)
            dp[i][k] = (dp[i-1][k]+dp[i][k-1])%10007;
 
    int total = 0;
    for (int i = 0; i < 10; i++) total += (dp[i][N])%10007;
    cout << total%10007;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

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

BOJ 2156번 포도주 시식  (0) 2020.01.06
BOJ 9465 스티커  (0) 2020.01.06
BOJ 2447번 별 찍기 - 10  (0) 2020.01.06
BOJ 10844번 쉬운 계단 수  (0) 2020.01.06
BOJ 3943번 헤일스톤 수열  (0) 2019.11.25

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

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

 

별찍기 튜토리얼중에 가장 어려웠던 것 같다.

그만큼 별찍기 문제중 유명한 문제이기도 하다.

 

힌트는 3의 제곱수라는 것과, 공백 좌표를 유심히 봐야하는 것이다.

옆의 사진에서 보면 n = 9 기준에서 공백이 되는 좌표는

(1,1) (1,4) (1,7) (4,1) ...

그리고 정중앙에 텅비게되는 (3,3) (3,4) (3,5) ...

 

이 숫자들을 싹다 3으로 나누어본다.

3으로 나누어보면서 알게되는 규칙은

현재 좌표 dx, dy 를 3으로 나눈 나머지가 둘다 1인 경우

그 지점은 공백이 되는 지점이라는 것이다.

어느 한 좌표라도 나머지가 1이 아니라면 그곳은 * 이 되는 지점이다.

 

이를 이용하여 코드를 구현하였다.

 

더보기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
 
    int N; cin >> N;
 
    for (int i = 0; i < N; i++) {
        for (int k = 0; k < N; k++) {
            int dx = i, dy = k;
            while (1) {
                if (dx == 0 || dy == 0) break;
                if (dx % 3 == 1 && dy % 3 == 1) break;
                dy /= 3, dx /= 3;
            }
            if (dx && dy) cout << " ";
            else cout << "*";
        }
        cout << "\n";
    }
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

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

BOJ 9465 스티커  (0) 2020.01.06
BOJ 11057번 오르막 수  (0) 2020.01.06
BOJ 10844번 쉬운 계단 수  (0) 2020.01.06
BOJ 3943번 헤일스톤 수열  (0) 2019.11.25
4673번 : 셀프넘버 - junnnho  (0) 2019.09.26

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

GitHub : https://github.com/junho0956/Algorithm/blob/master/10844/10844/%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
#include <iostream>
#include <cstring>
using namespace std;
#define MOD 1000000000
int dp[10][101];
 
// start_num : 현재 숫자
// len : 확인해야할 남은 자릿수
int dfs(int start_num, int len) {
// 0 미만 9 초과의 범위는 계산하지 않는다.
    if (start_num < 0 || start_num > 9) return 0;
 
// 이미 계산된 수는 더이상 계산할 필요 없으므로 그대로 가져다쓴다.
    if (dp[start_num][len] != -1) return dp[start_num][len];
 
// 현재 dp 가 가져야 할 값은
// 현재 숫자에서 -1,+1 을 한 재귀형식을 더한 값이다.
    dp[start_num][len] = (dfs(start_num - 1, len - 1) + dfs(start_num + 1, len - 1)) % MOD;
    return dp[start_num][len];
}
 
int main() {
    ios::sync_with_stdio(false);
 
    int N, total = 0;
    cin >> N;
 
    memset(dp, -1, sizeof(dp));
// 1자리수는 기본적으로 1가지밖에 없다.
    for (int i = 0; i <= 9; i++) dp[i][1] = 1;
 
// 0부터 시작하면 안되므로 1부터 시작한다.
// 이때 시작의 의미는 첫번째 자리숫자를 의미.
    for (int i = 1; i <= 9; i++) {
        total += dfs(i, N);
        total %= MOD;
    }
    
    cout << total;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

 

복습 20.02.20 꽤 쉽게 풀었다.

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

BOJ 11057번 오르막 수  (0) 2020.01.06
BOJ 2447번 별 찍기 - 10  (0) 2020.01.06
BOJ 3943번 헤일스톤 수열  (0) 2019.11.25
4673번 : 셀프넘버 - junnnho  (0) 2019.09.26
scpc 2019 예선 1차 2번 문제 : 공 굴리기 - Junnnho  (0) 2019.07.04

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

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

 

요구하는 그대로 따라가주면 되는 문제.

단, iostream을 사용할 것이라면 테스트케이스가 10만개이므로

ios::sync_with_stdio(false); 을 사용해주도록 하자.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstdio>
#include <algorithm>
using namespace std;
#pragma warning(disable:4996)
 
int main() {
    int T;
    scanf("%d", &T);
 
    while (T--) {
        long long n;
        scanf("%lld", &n);
 
        long long ans = 1;
        while (n != 1) {
            ans = max(ans, n);
            if (n % 2) n = n * 3 + 1;
            else n /= 2;
        }
        printf("%lld\n", ans);
    }
 
    return 0;
}

 

 

복습) 20.02.08

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

BOJ 2447번 별 찍기 - 10  (0) 2020.01.06
BOJ 10844번 쉬운 계단 수  (0) 2020.01.06
4673번 : 셀프넘버 - junnnho  (0) 2019.09.26
scpc 2019 예선 1차 2번 문제 : 공 굴리기 - Junnnho  (0) 2019.07.04
scpc 2019 예선 1차 1번 문제 : 오르락 내리락 - Junnnho  (0) 2019.07.04

+ Recent posts

티스토리툴바