백준14649 문홍안

작성일 | In

문제 링크

  • https://www.acmicpc.net/problem/14649

문제 출처

  • 제1회 천하제일 코딩대회 예선 E번

시간복잡도

  • O(n)

풀이

비서가 동시에 움직이는 것과 각자 움직이는 것의 결과는 같습니다. (밟은 횟수 동일)
방향이 l이면 1부터 pos-1까지의 돌을 밟고
방향이 r이면 pos+1부터 100까지의 돌을 밟습니다. (처음에 서있던 돌의 색은 바뀌지 않는다.)

  1. p, n을 입력받습니다.
  2. n명의 비서의 처음 위치와 방향을 입력받습니다.
  3. 방향에 따라 해당 범위를 지나는 시뮬레이션을 진행합니다.
  4. 돌의 개수에 따라 비례배분합니다.
  5. 비례배분 한 결과를 출력합니다.

전체 코드

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>

struct P{
	int pos, dir;
};

double p;
int n, arr[110]={0};
P people[110];
int r, g, b;

int main(){
	scanf("%lf %d", &p, &n);
	for(int i=1; i<=n; i++){
		int a; char b;
		scanf("%d %c", &a, &b);
		P tmp;
		tmp.pos=a;
		tmp.dir = (b=='L' ? -1 : 1);
		people[i] = tmp;
	}

	for(int i=1; i<=n; i++){
		if(people[i].dir  == -1){
			for(int j=people[i].pos-1; j>=1; j--) arr[j]++;
		}

		if(people[i].dir == 1){
			for(int j=people[i].pos+1; j<=100; j++) arr[j]++;
		}
	}

	for(int i=1; i<=100; i++){
		if(arr[i]%3==0) b++;
		if(arr[i]%3==1) r++;
		if(arr[i]%3==2) g++;
	}

	printf("%.2f %.2f %.2f", p*b/(r+g+b), p*r/(r+g+b), p*g/(r+g+b));
}