'알고리즘 풀이' 카테고리의 글 목록 (3 Page)

알고리즘 풀이

백준 8979 올림픽

2018. 8. 29. 03:37

<링크>

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

<소스코드>

#include<stdio.h>
#include<algorithm>
using namespace std;
typedef struct C {
    int n, g, s, b,r;
} C;
int compare(C c1, C c2)
{
    if (c1.g != c2.g)
        return c1.g > c2.g;
    if (c1.s != c2.s)
        return c1.s > c2.s;
    if (c1.b != c2.b)
        return c1.b > c2.b;
}
int main()
{
    C arr[1000];
    int N, K;
    scanf("%d%d", &N, &K);
    for (int i = 0; i < N; ++i)
    {
        int a, b, c, d;
        scanf("%d%d%d%d", &arr[i].n, &arr[i].g, &arr[i].s, &arr[i].b);
    }
    sort(arr, arr + N, compare);
    int i = 0;
    while (i < N)
    {
        int j = i;
        while (j < N && arr[j].g == arr[i].g && arr[j].s == arr[i].s && arr[j].b == arr[i].b)
        {
            arr[j].r = i;
            ++j;
        }
        i = j;
    }
    for(int i=0;i<N;++i)
    {
        if (arr[i].n == K)
            printf("%d", arr[i].r + 1);
    }
}

Colored by Color Scripter

<풀이>

처음엔 점수로 환산해서 풀어볼까 생각했지만

금:10점 은:5점 동:2점 이런식으로하면

은메달이 3개면 금메달 1개딴 나라보다 등수가 높아지게 된다.

여기서 생각을 멈췄기 때문에 노가다로 풀었다.

하지만 아무리 은메달을 많이 따도 금메달 1개 점수보다 작게끔 만들면 얘기가 달라진다.

메달 총개수는 100만개이므로 적절한 선을 찾으면 된다.

금메달 1개, 은메달 99만9999개를 땄을때

금메달의 점수가 은메달의 점수보다 100만배이상 차이나면 가능하다.

은메달과 동메달도 마찬가지다

동메달 : 1점

은메달 : 10^6점

금메달 : 10^12점 이면 충분히 가를 수 있다.

그렇게 총점을 환산한 후 나보다 잘한 국가들이 몇개있는지만 찾아주면 된다.

<소스코드>

#include <stdio.h>
long long a[1001];
int main() {
    int N, K;
    scanf("%d%d", &N, &K);
    for (int i = 1; i<=N; ++i) {
        int n, g, s, b;
        scanf("%d%d%d%d", &n, &g, &s, &b);
        a[n] = g* 1e12 + s* 1e6 + b;
    }
    int ans = 1;
    for (int i = 1; i <=N; ++i) {
        if (a[i] > a[K]) ++ans;
    }
    printf("%d", ans);
    return 0;
}

Colored by Color Scripter

저작자표시

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

백준 1991 트리 순회 (0)	2018.08.31
백준 2621 카드게임 (0)	2018.08.28
백준 13414 수강신청 (0)	2018.08.02
백준 13413 오셀로 재배치 (0)	2018.08.01
백준 10973 이전 순열 (0)	2018.07.24

백준 2816 디지털 티비

2018. 8. 29. 02:40

<링크>

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

<소스코드>

#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");
}

Colored by Color Scripter

<풀이>

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

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

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

저작자표시

백준 1110 더하기 사이클

2018. 8. 29. 01:46

<링크>

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

<소스코드>

#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);
}
 

<풀이>

걍 시키는대로하면된다.

저작자표시

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

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

백준 2621 카드게임

2018. 8. 28. 21:27

<링크>

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

<소스코드>

#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);
 
}

Colored by Color Scripter

<풀이>

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

예를들어 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

백준 1652 누울 자리를 찾아라

2018. 8. 28. 18:41

<링크>

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

<소스코드>

#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;
}

Colored by Color Scripter

<풀이>

길이가 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

PREV 1 2 3 4 5 6 ···12 NEXT

들짐승 프로그래밍