[백준 BOJ] 1138 한 줄로 서기

1138_한 줄로 서기

링크

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

 

풀이

 

자기가 줄을 서는 사람의 입장이 되봅시다. 작은 사람부터 세운다고 생각하면 그 이후에 들어오는 사람들은 다 현재 사람보다 큰 사람이기 때문에 현재 줄에 있는 빈 자리들은 모두 큰 사람들의 자리라고 생각하면 됩니다.

 

i가 현재 줄 세울 사람의 키, j가 그 사람이 설 자리, cnt가 자신보다 큰 사람(즉, 빈자리) 카운트 하는 변수, tmp가 왼쪽에 자기보다 키가 큰 사람이 몇 명 있었는지를 나타냅니다.

 

i의 키를 가진 사람이 j번째 자리를 봤을 때, 사람이 있는 경우에는 그 사람이 나보다 작기 때문에 cnt는 증가하지 않고, j만 증가합니다. 즉, 자리만 이동한다는 얘기죠.

그리고 if로 cnt와 tmp가 같을 때, j번째 자리에 i의 키를 가진 사람을 세웁니다.

증감식은 j++, cnt++로 자리 이동과 빈자리이기 때문에 카운트도 증가시켜 줍니다.

 

그렇게 해서 마지막에 줄을 출력하면 됩니다.

 

코드

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

//1138_한 줄로 서기 #include <cstdio> using namespace std;   int arr[11], tmp, n;   int main() {     scanf("%d", &n);       for (int i = 1; i <= n; ++i) {         scanf("%d", &tmp);         int j = 1, cnt = 0;         while (true) {             if (arr[j]) {                 j++;                 continue;             }               if (cnt == tmp) {                 arr[j] = i;                 break;             }                          j++, cnt++;         }     }       for (int i = 1; i <= n; ++i) printf("%d ", arr[i]);       return 0; } Colored by Color Scripter

cs