굳건하게

안녕하세요.

여행벌입니다.

오늘은 ACM-ICPC 2013 예선전 문제인 'KCPC' 풀이를 해보겠습니다.

단순 구현 문제로 문제 조건들만 잘 읽어준다면, 쉽게 풀 수 있습니다.

[문제해석]

1 ~ N 개의 팀이 있고, 1 ~ M 개의 문제가 있다고 하자.

문제마다 얻을 수 있는 점수는 0 ~ 100점이고, 팀 최종 점수는 모든 문제에서 획득한 점수의 합이라고 하자.

만약에 팀 최종 점수가 같다면 제출 횟수가 적은 팀이, 최종 점수와 제출 횟수고 같다면 마지막 제출이 더 빠른 팀이 이기고 동시에 서로 다른 팀이 문제를 제출하는 경우는 없다고 하자.

이때, 내가 속한 팀은 몇 등인지 출력하라.

[알고리즘설계]

Problem_Score[x][y] : x팀의 y번 문제에 대한 최대 점수.

total_socre[x] : x팀의 최종 점수.

count[x] : x팀의 문제 제출 횟수.

time[x] : x팀의 마지막 제출 시간.

위와 같은 배열을 4개 선언해주고 문제 해석에 맞춰서 구현을 진행하면 된다.

#include<iostream>

using namespace std;

int main(void){
	ios::sync_with_stdio(false);
	cin.tie(0);

	//freopen("input2.txt", "r", stdin);
	int test_case;
	cin >> test_case;
	for(int i = 0; i < test_case; i++){
		int nteams, nproblems, myid, nlog;
		cin >> nteams >> nproblems >> myid >> nlog;
		
		int team_problem[101][101]={};
		int count[101]={};
		int time[101]={};
		int total_score[101]={};

		for(int j = 1;j <= nlog; j++){
			int x,y,z;
			cin >> x >> y >> z;
			if (team_problem[x][y] < z)
				team_problem[x][y] = z;
			count[x]++;
			time[x] = j;
		}

		for (int j = 1; j <= nteams; j++){
			for (int k = 1; k <= nproblems; k++){
				total_score[j] += team_problem[j][k];
			}
		}

		int rank = 1;

		for (int j = 1; j <= nteams; j++){
			if(j == myid)
				continue;
			if(total_score[j] > total_score[myid])
				rank++;
			if(total_score[j] == total_score[myid]){
				if(count[j] < count[myid])
					rank++;
				if(count[j] == count[myid]){
					if(time[j] < time[myid])
						rank++;
				}
			}
		}
		cout << rank << '\n';

	}
}

열심히 공부하고 노력하고 있는 꿈 많은 예비 개발자입니다.
혼자서 공부한 내용을 정리하고 포스팅하다 보니 틀린 내용이 있을 수도 있습니다.
많은 조언과 가르침 주실 분은 댓글로 자유롭게 남겨주셔도 좋을 것 같습니다! 
감사합니다.

안녕하세요.

여행벌입니다.

ACM-ICPC 2013 예선전 문제인 'Registration' 을 다뤄보겠습니다.

네... 그냥 맞추라고 준 문제라 따로 설명없이 코드 올리겠습니다.

#include<stdio.h>

int main(void){
    printf("10\n");
    printf("travelbeeee");
}

열심히 공부하고 노력하고 있는 꿈 많은 예비 개발자입니다.
혼자서 공부한 내용을 정리하고 포스팅하다 보니 틀린 내용이 있을 수도 있습니다.
많은 조언과 가르침 주실 분은 댓글로 자유롭게 남겨주셔도 좋을 것 같습니다! 
감사합니다.

안녕하세요.

여행벌입니다.

오늘은 ACM-ICPC 2012 예선전 문제인 'Order'를 다뤄보겠습니다.

문제를 읽었을 땐 되게 어렵다고 느꼈지만, 간단한 아이디어로 구현할 수 있어서 금방 해결한 문제입니다.

[문제해석]

N명의 사람이 일렬로 서있고, 모든 사람들은 1 ~ N까지 숫자 중에 겹치지 않게 숫자를 하나 부여받는다고 하자.

이때, N개의 값이 주어지고 이 값들은 왼편에 있는 사람 중 나보다 값이 적은 사람의 수라고 하자.

N개의 값이 유효한지 아닌지 판단해라.

위의 예제를 통해 문제를 조금 더 이해해보자.

10명의 사람이 있고 [0 0 0 2 0 1 6 7 6 9] 라는 배열이 주어졌을 때, [6 4 3 5 1 2 8 9 7 10] 배열에 대해 생각해보자.

'4'번 번호를 부여받은 사람은 왼쪽에 자기보다 큰 '6' 만 존재하고,

'3'번 번호를 부여받은 사람은 마찬가지로 왼쪽에 자기보다 큰 '6', '4' 만 존재하므로 [0 0 0 ~ ]이 되고,

'5'번 번호를 부여받은 사람은 왼쪽에 자기보다 작은 '4', '3' 존재하므로 [0 0 0 2 ~ ]이 성립한다.

[알고리즘설계]

1. N개의 배열이 주어졌을 때, 이 배열은 왼쪽에 나보다 작은 사람의 수를 의미하므로 앞에서부터 순회하며 내 오른쪽에는 사람이 없다고 가정하고 왼쪽 사람들에게만 초점을 맞춰서 번호를 갱신하자.

ex)

[0 0 0 2 0 1 6 7 6 9 ] 가 입력된다고 하자.

1번 사람은 왼쪽에 자기보다 작은 사람이 0명이므로 가장 큰 번호인 1을 부여한다. [ 1 ]

2번 사람은 왼쪽에 자기보다 작은 사람이 0명이므로 가장 큰 번호인 2를 부여한다. [ 1 2 ]

3번 사람도 마찬가지로 3을 부여하고 [ 1 2 3 ] 이 된다.

4번 사람은 작은 사람이 2명이므로 번호 3을 부여하고, 3보다 크거나 같은 번호를 하나씩 업시켜준다. [ 1 2 4 3 ]

5번 사람은 작은 사람이 0명이므로 가장 큰 번호인 5를 부여한다. [ 1 2 4 3 5 ]

6번 사람은 작은 사람이 1명이므로 2번 번호를 부여하고, 2번보다 크거나 같은 번호들은 하나씩 업시켜준다.

[1 3 5 4 6 2] 가 된다.

2. 왼쪽에 있는 사람의 수보다 나보다 작은 사람의 수가 더 큰 경우에는 "IMPOSSIBLE"을 출력하자.

ex)

[0 0 0 5  ~~ ]

4번 사람은 왼쪽에 3명밖에 없는데 작은 사람이 5명이므로 불가능한 경우다.

#include<cstdio>

int s[100] = {};
int r[100] = {};

int main(void) {
	int test_case;
	scanf("%d", &test_case);

	for (int i = 0; i < test_case; i++) {
		int ninput, flag = 0;
		scanf("%d", &ninput);

		for (int j = 0; j < ninput; j++){
			scanf("%d", &r[j]);
		}

		for (int j = 0; j < ninput; j++) {\
			if (j < r[j]) {
				printf("IMPOSSIBLE\n");
				flag = 1;
				break;
			}

			s[j] = r[j];
			for (int k = 0; k < j; k++) {
				if (s[k] >= r[j])
					s[k]++;
			}
		}

		if (flag)
			continue;

		for (int j = 0; j < ninput; j++)
			printf("%d ", s[j] + 1);
		printf("\n");
		
	}
}

열심히 공부하고 노력하고 있는 꿈 많은 예비 개발자입니다.
혼자서 공부한 내용을 정리하고 포스팅하다 보니 틀린 내용이 있을 수도 있습니다.
많은 조언과 가르침 주실 분은 댓글로 자유롭게 남겨주셔도 좋을 것 같습니다! 
감사합니다.

안녕하세요.

여행벌입니다.

오늘은 ACM-ICPC 2012 예선전 'Parenthesis' 문제를 다뤄보겠습니다.

대표적인 스택 자료구조를 이용한 문제로 쉽게 풀 수 있었습니다.

[문제해석]

주어진 문자열이 괄호가 제대로 짝이 맞는지 안 맞는지 판단해서 맞는다면 "YES" 아니라면 "NO"를 출력해라.

[알고리즘설계]

( ( ) ) ( ) ) 같은 경우는 앞에 4개 (  (  ) )  와 그 뒤 2개  ( ) 는 짝이 맞지만 마지막 ) 의 짝꿍이 없으므로 NO이다.

이처럼 우리는 지금 주어진 괄호가 짝궁이 있는지 없는지 판단하면 된다.

1. Stack 자료구조를 이용해서, ' ( ' 인 경우에는 Stack에 넣고, ' ) ' 인 경우에는 Stack에서 하나를 꺼내서 짝꿍을 맺어준다. 이때, ' ) ' 인 경우지만 Stack이 비어있다면 짝꿍이 없는 경우이므로 'NO'를 출력하고 또, 끝까지 진행했는데 아직 Stack에 남아있는 ' ( ' 가 존재해도 짝궁이 없는 경우이므로 'NO'를 출력한다. 이 외에는 "YES"를 출력해준다.

#include<iostream>
#include<stack>
#include<string>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int ninput;
	cin >> ninput;
	for (int i = 0; i < ninput; i++) {
		stack<int> list;
		string input;
		cin >> input;
		int flag = 0;
		for (int j = 0; j < input.length(); j++) {
			if (input[j] == '(')
				list.push(j);
			if (input[j] == ')') {
				if (list.empty()) {
					cout << "NO\n";
					flag = 1;
					break;
				}
				else
					list.pop();
			}
		}
		if (list.empty() && flag == 0)
			cout << "YES\n";
		else if (!list.empty() && flag == 0)
			cout << "NO\n";
	}
}

Stack 자료구조를 배울 때, 같이 배우는 대표적인 문제라 금방 해결할 수 있었습니다.

열심히 공부하고 노력하고 있는 꿈 많은 예비 개발자입니다.
혼자서 공부한 내용을 정리하고 포스팅하다 보니 틀린 내용이 있을 수도 있습니다.
많은 조언과 가르침 주실 분은 댓글로 자유롭게 남겨주셔도 좋을 것 같습니다! 
감사합니다.