출처:  http://usaco.org/index.php?page=viewproblem2&cpid=1180

문제 설명

4면체 주사위 3개(A, B, C) 가 있고, 주사위의 각 면의 숫자는 1부터 10 사이의 숫자이다. 두 주사위를 던져서 높은 숫자가 많이 나오는 주사위가 이겼다고 할때, A > B > C > A 혹은 A < B < C < A 가 되는 조합이 있는지 판별하는 문제이다. 입력으로는 주사위 A, B의 숫자들이 주어진다.

입력

3
4 5 6 7 2 4 5 10
2 2 2 2 1 1 1 1
1 1 1 1 2 2 2 2

출력

yes
no
no

 

문제 풀이

주사위 C의 숫자들이 1 ~ 10 이고, 4개의 숫자를 선택할때 가능한 모든 조합 O(N^4)를 해도 10^4 이고, 주사위 2개를 비교해서 편정하는 경우도 4^2 이므로, 전체 계산량은 대략 10^5 정도로 가능하다. 중첩된 Loop 로 모든 경우를 비교하는 알고리즘으로 가능하다. 

프로그램 내용

더보기 
...
for(i)
	for(j)
    	for(k)
        	for(l)
            	dice_c = {i, j, k, l}
                if( dice_c >dice_b && dice_b >dice_a && dice_a > dice_c)
                	flag = true; break;
				if( dice_b >dice_c && dice_a >dice_b && dice_c > dice_a)
                	flag = true; break;
if(flag)
	cout << "yes"
else
	cout << "no"

 

저작자표시 비영리 동일조건

'USACO' 카테고리의 다른 글

USACO 2022 January Bronze Problem 1  (0) 2022.02.04

출처: 2022 January Bronze Problem 1 ( link )

문제 설명

3X3 charater puzzle

- Green: correct

- Yellow: Mis location

입력 1

COW
SAY
MOO
WIN
THE
IOI

출력

1

1

입력 2

AAA
BBB
CCC
AYY
AAA
ZZZ

출력 

1

2

문제 풀이

문자열 비교를 어떻게 할 것인가 하는 문제이다. 입력으로 주어진 3 x 3 퍼즐을 1 x 9 형태로 바꿔도 문제 풀이에 영향은 없다. char[9] 인 두개의 배열/vector를 만들어서 예상 답안과 실제 답안을 입력하고, 전체를 비교해서 같으면 Green 값에 반영한다.  다음은, 두 답안의 A~Z의 빈도를 확인해서, 잘못된 위치지만 있었는지 확인해서 Yellow 값에 반영한다. 다만, Green 에 반영된 결과를 두번 세지 않도록 해줘야 한다.

프로그램 내용

더보기 
// serialization & count frequency 

	for(int i = 0; i<3; ++i)
    {
        string tmp;
        cin >> tmp;
        ans += tmp;
        ans_cnt[tmp[0]-'A']++;
        ans_cnt[tmp[1]-'A']++;
        ans_cnt[tmp[2]-'A']++;
    }
    
    for(int i = 0; i<3; ++i)
    {
        string tmp;
        cin >> tmp;
        gus += tmp;
        gus_cnt[tmp[0]-'A']++;
        gus_cnt[tmp[1]-'A']++;
        gus_cnt[tmp[2]-'A']++;
    }

// cnt_g & cnt_y
    for(int i = 0; i<9; ++i)
    {
        if(ans[i] == gus[i])
            cnt_g++;
    }

    for(int i = 0; i<26; ++i)
    {
        cnt_y += min(ans_cnt[i],gus_cnt[i]);
    }

    cnt_y -= cnt_g;

 

저작자표시 비영리 동일조건

'USACO' 카테고리의 다른 글

USACO 2022 January Bronze Problem 2  (0) 2022.02.21

+ Recent posts

티스토리툴바