<링크>

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


<소스코드>

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<stdio.h>
#include<string.h>
int main()
{
    int N;
    scanf("%d", &N);
    int index[2];
    char buf[11];
    for (int i = 0; i < N; ++i)
    {
        scanf("%s", buf);
        if (strcmp(buf, "KBS1") == 0)
            index[0] = i;
        if (strcmp(buf, "KBS2") == 0)
            index[1] = i;
    }
    int add = index[0] > index[1];
    for (int i = 0; i < index[0]; ++i)
        printf("1");
    for (int i = 0; i < index[0]; ++i)
        printf("4");
    for (int i = 0; i < index[1] + add; ++i)
        printf("1");
    for (int i = 0; i < index[1] + add - 1; ++i)
        printf("4");
}
cs


<풀이>

스페셜저지이고 어차피 명령길이가 500만 안넘으면 되기 때문에

1이랑 4로만 처리하려했다. 올릴때는 무조건 KBS1먼저 싹 올리고 그다음에 KBS2를 올렸다.

이런 방식에서 KBS2가 KBS1보다 먼저나오면 KBS1을 올리는과정에서 KBS2의 원래 위치가 하나 밀려내려가기 때문에 누가 먼저 나오는지 체크했다.


저작자표시

<링크>

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


<소스코드>

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
#include<stdio.h>
#include<algorithm>
#include<string>
#include<string.h>
#include<iostream>
#pragma warning(disable:4996)
 
using namespace std;
int main()
{
    int N;
    scanf("%d", &N);
    int cnt = 0;
    int ori = N;
    while (true)
    {
        ++cnt;
        int a = ori/ 10;
        int b = ori % 10;
        int c = b*10+(a + b)%10;
        
        if (c == N)
            break;
        ori = c;
        
        
    }
    printf("%d", cnt);
}
 
cs


<풀이>

걍 시키는대로하면된다.


저작자표시

'알고리즘 풀이 > 수학' 카테고리의 다른 글

백준 1652 누울 자리를 찾아라  (0) 2018.08.28
백준 1722 순열의 순서  (0) 2018.07.26

<링크>

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


<소스코드>

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
68
69
70
71
72
73
74
75
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
int main() {
    int ans = 0;
 
    vector<pair<int,char>> card;
    int cnt[10] = { 0, };
    string buf;
    int maxNum = 0;
    for (int i = 0; i < 5; ++i)
    {
        getline(cin, buf);
        char c = buf[0];
        int n = buf[2] - '0';
        card.push_back({ n,c}); //숫자, 색깔
        maxNum = max(maxNum,n);
        cnt[n]++;
    }
 
 
 
    int colorCheck = 1;
    int seqCheck = 1;
    sort(card.begin(), card.end());
    char c = card[0].second;
    for (int i = 1; i < 5; ++i)
    {
        if (c != card[i].second)
            colorCheck = 0;
        if (card[i].first != card[i - 1].first + 1)
            seqCheck = 0;
    }
    if (colorCheck)
        ans = max(ans, 600 + maxNum);
    if (seqCheck)
        ans = max(ans, 500 + maxNum);
    if (colorCheck && seqCheck)
        ans = max(ans, 900 + maxNum);
 
    vector<pair<int, int>> v;
    for (int i = 1; i <= 9; ++i)
        if (cnt[i])
            v.push_back({cnt[i],i });
    sort(v.begin(), v.end(),greater<pair<int,int>>());
    
    if (v[0].first >= 4)
        ans = max(ans,v[0].second + 800);
    else if (v[0].first == 3)
    {
        if (v[1].first == 2)
            ans = max(ans,v[0].second * 10 + v[1].second + 700);
        else
            ans = max(ans,v[0].second + 400);
    }
    else if (v[0].first == 2)
    {
        if (v[1].first == 2)
        {
            int m = max(v[0].second, v[1].second);
            int n = min(v[0].second, v[1].second);
            ans = max(ans,m * 10 + n + 300);
 
        }
        else
            ans = max(ans,v[0].second + 200);
    }
    else
        ans = max(ans,maxNum + 100);
    
    printf("%d", ans);
 
}
cs


<풀이>

걍 조건문 잘 만드는 문제인데 낚시가 있을것같았다. 

예를들어 R5, Y5, G7, B5, Y7 일때, 

같은숫자가 3개&2개인데 2개&2개도 적용이 된다. 

상식상 카드게임할때 3&2가 2&2보다 더 운좋은거니까 높은점수를 먹을것같았는데

2개&2개로 계산하는게 10을 곱하고 어쩌고가 있어서 더 클수도있을것같았다.

그래서 규칙들을 적용했을 때 나올수 있는 점수 범위를 보니까

<규칙 : 나올수있는점수>

●9번규칙 : 101~109점
●8번규칙(2) : 201~209점
●7번규칙(2&2) : 311~399점
●6번규칙(3) : 401~409점
●3번규칙(3&2) : 711~799점
●2번규칙(4) : 801~809점

하위규칙에서 아무리 잘나와봤자 상위규칙의 제일 못한놈을 이길수는 없다.

그래서 규칙적용 순서만 잘 적용시키면 최대점수를 알수있게 된다.


<카드 숫자 빈도 : 규칙>

●5 : 2번규칙
●4 1 : 2번규칙
●3 2 : 3번규칙
●3 1 1 : 6번규칙
●2 2 1 : 7번규칙
●2 1 1 1 : 8번규칙
●1 1 1 1 1 : (1 or 4 or 5 or 9번규칙)

저작자표시

'알고리즘 풀이 > 기타' 카테고리의 다른 글

백준 1991 트리 순회  (0) 2018.08.31
백준 8979 올림픽  (0) 2018.08.29
백준 13414 수강신청  (0) 2018.08.02
백준 13413 오셀로 재배치  (0) 2018.08.01
백준 10973 이전 순열  (0) 2018.07.24

<링크>

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


<소스코드>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<cstdio>
char pan[101][101];
int main() {
    int N, r, c;
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
        scanf("%s", pan[i]);
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N - 1; j++)
            r += pan[i][j] == '.' && pan[i][j + 1] == '.' && pan[i][j + 2] != '.',
            c += pan[j][i] == '.' && pan[j + 1][i] == '.' && pan[j + 2][i] != '.';
    printf("%d %d", r, c);
    return 0;
}
cs


<풀이>

길이가 2이던 그보다 길던 자리는 1개로 치기 때문에


.........x 이렇게 있는경우랑

..x 이렇게 있는 경우랑 둘다 하나의 자리로 친다.


그럼 ..x인 순간만 찾아내면 된다.


.........x...x....x..x

자리가 이렇게 있으면


.......(..x).(..x)..(..x)(..x) 총 4자리가 난다



..x.. 

이런상황이면

(..x)(..) 총 두자리가 난다.

N*N보다 배열 크기를 더 잡아주면 남은 공간엔 0이 들어가있다.

그래서 우측벽은

위의 코드에서

pan[i][j+2]!='.' 에 해당하므로 

..x

..벽

두가지 다 답으로 더해지게 된다.


가로, 세로를 한번에 보려고 (i,j) (j,i)를 동시에 체크했다.

저작자표시

'알고리즘 풀이 > 수학' 카테고리의 다른 글

백준 1110 더하기 사이클  (0) 2018.08.29
백준 1722 순열의 순서  (0) 2018.07.26

<링크>

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


<소스코드>

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<stdio.h>
#include<math.h>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
int p[2000001];
vector<int> v;
void sieve();
int isPal(int);
int main()
{
    sieve();
    for (int i = 2; i <= 2000000; ++i)
        if (!p[i] && isPal(i))
            v.push_back(i);
    int N;
    scanf("%d", &N);
    printf("%d", *lower_bound(v.begin(), v.end(), N));
}
int isPal(int n)
{
    string s = to_string(n);
    int i = 0;
    int j = s.length() - 1;
    while (i <= j)
    {
        if (s[i] != s[j])
            return 0;
        ++i;
        --j;
    }
    return 1;
 
}
void sieve()
{
    int s = sqrt(2000000);
    for (int i = 2; i <= s; ++i)
    {    
        if(!p[i])
        for (int j = i * 2; j <= 2000000; j += i)
        {
            p[j] = 1;
        }
    }
}
cs


<풀이>

소수하면 걍 떠오르는게 에라토스테네스의 체라서 일단 그렇게 구현하려했는데,

100만보다 크면서 팰린드롬인 소수는 어디까지 가야 있을지를 모르겠었다.

즉 , 배열을 얼마만큼 잡아야할지 각이 안나왔다.

그래서 대충 200만까지 잡고 돌려봤다.

1003001이 출력될 수 있는 가장 큰 값이었다.


체를 이용해서 소수인 애들을 체크해놓고

팰린드롬인애들만 벡터에 집어넣었다.

팰린드롬인지 체크하는 시간은 (2~1003001 사이의 소수의 개수)*숫자의 길이이다.

수의 길이는 최대 7이므로 시간 내에 들어온다.

그래서 팰린드롬은 그냥 노가다로 체크했다.


N이상이면서 가장 작은 수를 출력해야 하기 때문에

lower_bound를 이용했다.


저작자표시

+ Recent posts

티스토리툴바