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

https://www.acmicpc.net/problem/4673

 

문제 해결에 필요한 알고리즘 : 소수(?)

 

특정 자연수에 대해서 생성자(자신을 만들어낼 수 있는 수) 가 없는 수를 셀프넘버 라고 한다는데

문제 힌트는 분명 소수 라고 되어있긴한데 소수로 어떻게 문제를 해결하는 것인지는 잘 모르겠고

그냥 각 수 마다 셀프넘버를 찾는 방식으로 문제를 해결하였다.

 

10000까지의 셀프넘버를 찾으면 되니

10000까지 전부 셀프넘버가 아닌 것으로 초기화하고

각 숫자마다 셀프넘버인지 확인 후, 반복문을 통하여 답을 출력하였다.

 

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
#include <cstdio>
 
int arr[10001];
int num[5], idx;
 
void selfNum(int N) {
    idx = 0;
    int k = N;
    while (N) {
        num[idx++] = N % 10, N /= 10;
    }
    for (int i = 0; i < idx; i++) {
        k += num[i];
    }
 
    arr[k] = 1;
}
 
int main() {
    for (int i = 1; i < 10001; i++) {
        selfNum(i);
    }
 
    for (int i = 1; i < 10001; i++)
        if (!arr[i]) printf("%d\n", i);
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter

 

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

BOJ 10844번 쉬운 계단 수  (0) 2020.01.06
BOJ 3943번 헤일스톤 수열  (0) 2019.11.25
scpc 2019 예선 1차 2번 문제 : 공 굴리기 - Junnnho  (0) 2019.07.04
scpc 2019 예선 1차 1번 문제 : 오르락 내리락 - Junnnho  (0) 2019.07.04
백준 2470번 : 두 용액 - Junnnho  (0) 2019.07.04

2번 문제는 살짝 수학문제 푸는 느낌

 

* 공의 지름보다 작은 장애물을 넘을 때 계산과정 *

 

지름보다 같거나 큰 장애물을 넘을 때는 그냥 반지름에 대한 90도의 호 길이만 구할 줄 알면 되는데

 

중요한 것은 지름보다 작은 장애물을 넘을 때는 호의 이동 길이가 달라진 다는 것이다.

 

* 종이에다가 지름보다 작은 장애물, 공을 그려놓고

  어떻게 움직이는 지 확인해보자.

  원의 방정식 (x-a)^2 + (y-b)^2 = r^2 을 안다면

  쉽게 해결할 수 있는 문제!

 

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
#include <iostream>
#define _USE_MATH_DEFINES
#include <math.h>
using namespace std;
 
 
int main() {
    int Test_case, T;
    double r, fx, lx;
    double bfx, bsx, bh, move;
 
    cin >> Test_case;
 
    for (int i = 1; i <= Test_case; i++) {
        move = 0;
 
        cin >> r >> fx >> lx >> T;
        cout << fixed;
        cout.precision(12);
        while (T--) {
            cin >> bfx >> bsx >> bh;
            double x = (M_PI * 2 * r) / 4;
            double m1 = (bfx - r) - fx;
            double m3 = bsx - bfx;
            double m2 = bh - r;
            double m4 = m2;
 
            if (bh < r) {
                m2 = m4 = 0;
                double distance = sqrt(r*r - (bh - r)*(bh - r));
                if (distance < 0) distance *= -1;
                distance = r - distance;
                double ceta = atan2((r-distance), (r - bh)) * 180/M_PI;
                x = x * (ceta / 90);
                m3 += distance * 2;
            }
 
            fx = bsx + r;
            move += m1 + m2 + m3 + m4 + x + x;
 
            if (T == 0) move += lx - fx;
        }
        cout << "Case #" << i << '\n' << move << '\n';
    }
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter

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

BOJ 3943번 헤일스톤 수열  (0) 2019.11.25
4673번 : 셀프넘버 - junnnho  (0) 2019.09.26
scpc 2019 예선 1차 1번 문제 : 오르락 내리락 - Junnnho  (0) 2019.07.04
백준 2470번 : 두 용액 - Junnnho  (0) 2019.07.04
에라토스테네스의 체  (0) 2019.06.30

1번 문제는 BOJ 1로 만들기 와 비슷하다 https://www.acmicpc.net/problem/1463

한창 DP 기본문제들 풀 때 풀었던 문제였는데

1번 문제를 보고 어디서 많이 본 느낌이 났었다.

 

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
#include <iostream>
using namespace std;
 
int dp[1000001];
int sum[1000001];
 
int main() {
    int T, num, num2;
    int Answer = 0;
    cin >> T;
 
 
    dp[1] = 0, dp[2] = 1, dp[3] = 3, dp[4] = 2, dp[5] = 5, dp[6] = 4;
 
    for (int i = 5; i < 1000001; i++) {
        if (i % 2 == 0) {
            dp[i] = dp[i / 2] + 1;
        }
        else if (i % 2 == 1) {
            dp[i] = dp[i / 2 + 1] + 2;
        }
    }
 
    for (int i = 1; i < 1000001; i++) {
        sum[i] += dp[i] + sum[i - 1];
    }
 
    for (int i = 1; i <= T; i++) {
        
        cin >> num >> num2;
 
        cout << "Case #" << i << '\n' << sum[num2] - sum[num - 1] << '\n';
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter

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

4673번 : 셀프넘버 - junnnho  (0) 2019.09.26
scpc 2019 예선 1차 2번 문제 : 공 굴리기 - Junnnho  (0) 2019.07.04
백준 2470번 : 두 용액 - Junnnho  (0) 2019.07.04
에라토스테네스의 체  (0) 2019.06.30
BOJ 11729번 하노이 탑 이동 순서  (0) 2019.05.31

+ Recent posts

티스토리툴바