How We Coding

[2529] 부등호

BOJ/Data Structure2018. 7. 22. 11:54

### Stack ###


[2529] 부등호 : http://boj.kr/2529


<소스코드>


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
#include <stdio.h>
 
int main()
{
    int n;
    int nextL=8, nextS=1;
    long long int ansL=9LL, ansS=0LL, ans=0LL;
    long long int arrL[10], arrS[10];
    int Lidx=0, Sidx=0;
    char buf[10];
    int factL=10, factS=10;
    scanf("%d", &n); 
 
    for(int i=0; i<n; i++) {
        char ch;
        scanf(" %c", &ch);
        if(ch == '<') {
            if(i == n-1 && nextL == 0) arrL[Lidx++] = 0LL;
            ansL = 1LL*nextL*factL + ansL;
            arrS[Sidx++] = ansS; ansS = nextS; factS = 1;
        }
        else {
            arrL[Lidx++] = ansL; ansL = nextL; factL = 1;
            ansS = 1LL*nextS*factS + ansS;
        }
        nextL--; factL *= 10;
        nextS++; factS *= 10;
    }
    arrL[Lidx++] = ansL;
    arrS[Sidx++] = ansS;
 
    for(int i=0; i<Lidx; i++) 
        printf("%lld", arrL[i]);
    puts("");
    for(int i=0; i<Sidx; i++)
        printf("%lld", arrS[i]);
    puts("");
 
    return 0;
}
cs


>> 큰수의 경우 '>' 를 만나기 전까지 앞에다 갱신을 해주면 된다 '<' 를 만나면 남은 최대값으로 반복.


>> 알고리즘 분류에 그리디와 위상정렬로 되어 있고, kks227 님도 위상정렬로 해설을 하셨는데, 

     한편으로 그리디는 맞다고 생각하지만, 위상정렬은 왜 위상정렬인지 아직도 모르겠다. 

    

>> 그럼에도 불구하고 스택으로 분류를 한 이유는 다른 사람이 스택으로 풀었기 때문이고, 아이디어는 내가 푼 것과 비슷하기 때문이다. 

>> 그분이 더 머리가 좋아보인다...ㅜ (아래는 그 코드)



- coded by t1234


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 <cstdio>
#include <stack>
int k, n=9;
char a[15];
std::stack<int> st;
 
void f() {
    while(!st.empty()) printf("%d", st.top()), st.pop();
}
 
int main() {
    int i;
    scanf("%d", &k);
    st.push(n--);
    for(i=0; i<k; i++) {
        scanf("%s", &a[i]);
        if(a[i]=='>') f();
        st.push(n--);
    }
    f();
    puts("");
    n = 0;
    st.push(n++);
    for(i=0; i<k; i++) {
        if(a[i]=='<') f();
        st.push(n++);
    }
    f();
    return 0;
}
cs



'BOJ > Data Structure' 카테고리의 다른 글

[5639] 이진 검색 트리  (0) 2018.07.22
[1655] 가운데를 말해요  (0) 2018.07.22

[RUNNINGMEDIAN] 변화하는 중간 값

PS/종만북2018. 7. 20. 01:58

[RUNNINGMEDIAN] 변화하는 중간 값 : https://algospot.com/judge/problem/read/RUNNINGMEDIAN


### 우선순위 큐 (힙) ###


<소스코드>


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 <cstdio>
#include <vector>
#include <queue>
using namespace std;
 
typedef long long int lli;
const lli MOD = 20090711LL; 
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        int n, b;
        lli a;
        scanf("%d%lld%d", &n, &a, &b);
 
        lli ai = 1983LL;
        lli ans = ai;
        priority_queue<lli> minH, maxH;
        maxH.push(ai);
        for(int i=1; i<n; i++) {
            ai = (1LL*ai*a+b)%MOD; 
            
            if(i&1) minH.push(-ai);
            else maxH.push(ai);
           
            if(-minH.top() < maxH.top()) {
                int a = maxH.top(); maxH.pop();
                int b = -minH.top(); minH.pop();
                maxH.push(b);
                minH.push(-a);
            }
            ans = (ans + maxH.top()) % MOD;
       }
        printf("%lld\n", ans);
    }
    return 0;
}
 
cs


>> 맥스힙에는 중간값 기준으로 중간값 포함, 그보다 작은 것들을, 민힙에는 중간값보다 큰 녀석들이 들어가게 된다. 


'PS > 종만북' 카테고리의 다른 글

[DICTIONARY] 고대어 사전  (0) 2018.05.22
[BOGGLE] 보글게임  (0) 2018.04.30
[MATCHORDER] 출전 순서 정하기  (0) 2018.04.20
[NUMBERGAME] 숫자게임  (0) 2018.04.17
[POLY] 폴리오미노  (0) 2018.04.16

<5-9> 전체탐색 - 마법의 숫자 (NumberMagicEasy)

PS/Topcoder training2018. 7. 16. 12:50

### 전체탐색 ###


### SRM 484 Div2 Level 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
#include <string>
using namespace std;
 
class NumberMagicEasy {
public:
    int theNumber(string answer) {
        int card[4][8] = {{1, 2, 3, 4, 5, 6, 7, 8},
                         {1, 2, 3, 4, 9, 10, 11, 12},
                         {1, 2, 5, 6, 9, 10, 13, 14},
                         {1, 3, 5, 7, 9, 11, 13, 15}};
        
        int cnt=0;
        int check[17]={0};
        for(int i=0; i<4; i++) {
            if(answer[i] == 'Y') {
                cnt++;
                for(int k=0; k<8; k++) 
                    check[card[i][k]]++;
            }
            else {
                for(int k=0; k<8; k++) 
                    check[card[i][k]]--;
            }
        }
       
        for(int i=1; i<=16; i++) {
            if(cnt == check[i])
                return i;
        }
        return 0;
    }
};
 
cs


>> 정답이 있는 카드들에 대한 교집합 - 정닶이 없는 카드에 대해 차집합

>> 정답 카드의 갯수만큼 카운트된 숫자가 정답이 된다.

'PS > Topcoder training' 카테고리의 다른 글

<5-8> 전체탐색 - 미로 만드는 사람 (MazeMaker)  (0) 2018.07.16
<8-8> 수학 - 둥근 모양의 국가들 (CirclesCountry)  (0) 2018.07.16
<8-4> 그리디 - 배치 시스템 (BatchSystem)  (0) 2018.07.16
<8-1> 탐색범위 한정 - 다양한 색상의 상자와 공 (ColorfulBoxesAndBalls)  (0) 2018.07.14
<7-5> DP - 악수 (HandShaking)  (0) 2018.07.04

티스토리툴바