C++ 백준 10157 자리 배정

알고리즘

C++ 백준 10157 자리 배정

Chars4785 2019. 1. 25. 20:45

달팽이 문제와 비슷하다.

주의 해야 할 점이 시작 위치가 (1,1) 이라는 점이다. 그래서 start를 {1,0} {0,0} 으로 해야 할지 고민 되지만 잘 생각하면

이미 x 좌표 1 은 증가 되어 있고 y 가 시작 부터 row 만큼 돌아야 해서 그렇다.

가로 세로 반대로 나오기 때문에 조심!!!

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

#include <iostream>

using namespace std;

int arry[1000][1000];

int main(){

   int col,row;
   cin >>col >>row;
   //7,6
   int H;
   cin >>H;
   //11

   // start ver

   int count =0;
   
   int start[2] = {1,0};
   int swit = 1;
   if(col * row <H)
   {
      cout<<"0"<<endl;
      return 0;
   }else{

      while(1)
      {
         //
         for(int i=0;i<row;i++)
         {
            start[1] += swit;
            count++;

            if(count == H) {
               cout<<start[0]<<" "<<start[1]<<endl;
               return 0;
            }

         }
      
         col--;

         for(int i=0;i<col;i++)
         {
            start[0] += swit;
            count++;
            if(count == H) {
               cout<<start[0]<<" "<<start[1]<<endl;
               return 0;
            }
         }

         row--;
         swit *= -1;

      }

   }  
  
   return 0;
}

-----------------------------

다른 풀이법

#include <stdio.h>

const int dx[] = { 1,0,-1,0 };
const int dy[] = { 0,1,0,-1 };

int n, m, c, a[1002][1002];

int main() {
	scanf("%d %d %d", &n, &m, &c);

	for (int i = 0; i <= 1001; i++) a[i][0] = a[0][i] = a[m + 1][i] = a[i][n + 1] = 1;

	int x = 0, y = 1, d = 0;
	for (int i = 1; i <= n*m; i++) {
		x += dx[d], y += dy[d];
		a[x][y] = 1;
		if (a[x + dx[d]][y + dy[d]]) d = (d + 1) % 4;
		if (i == c) {
			printf("%d %d", y, x);
			return 0;
		}
	}

	printf("0");

	return 0;
}

출처: http://wookje.dance/2017/09/17/boj-10157-%EC%9E%90%EB%A6%AC%EB%B0%B0%EC%A0%95/

재미있는 부분은

for (int i = 0; i <= 1001; i++) a[i][0] = a[0][i] = a[m + 1][i] = a[i][n + 1] = 1;

>>>

    int n,m,c;
    cin>>n >> m >>c;

   for (int i = 0; i <= 10; i++){

       cout<<i<<" "<<"0"<<endl;
       cout<<"0"<<" "<<i<<endl; 
       cout<<m+1<<" "<<i<<endl;
       cout<<i<<" "<<n+1<<endl;
       cout<<"------"<<endl;
   } 

0 0

7 0

0 8

------

1 0

0 1

7 1

1 8

------

2 0

0 2

7 2

2 8

------

3 0

0 3

7 3

3 8

------

4 0

0 4

7 4

4 8

------

5 0

0 5

7 5

5 8

------

6 0

0 6

7 6

6 8

------

7 0

0 7

7 7

7 8

------

8 0

0 8

7 8

8 8

------

9 0

0 9

7 9

9 8

------

10 0

0 10

7 10

10 8

------

결과로 보면

중간에 모두 쓰레기 값으로 두고 주변을 1로 둘러싸는 방법이다.

재미있는 발상인듯 하다.

| 0 1 2 3 4 5 6 7 8 9

-----------------------------------------------------------------

0 | 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ......

1 | 1 1

2 | 1 1

3 | 1 1

4 | 1 1

5 | 1 1

6 | 1 1

7 | 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ......

8 | 1

9 | 1

.....