2016/01/31 코드그라운드 문제 : 미궁 속의 방

https://www.codeground.org/practice/practiceProbView.do?probId=6#

생각할 점
1. 방 크기인 N이 10만까지인데 배열을 만들어서 숫자를 쓸 경우 N제곱 백억개의 배열을 만들어야하고 int가 unsigned로 선언해도 4억까지니 double 배열을 만들어야 하는데
그럴 경우 메모리를 8백억byte 사용해야 한다. 메모리 제한 256MB로는 대략 2억6천 바이트 int형의 경우 5천만 개 정도 생성할 수 있다.
배열로 풀 문제는 아니다.
2. 행과 열의 조합으로 숫자를 구해야 한다. 1~n까지 더한 값은 n*(n+1)/2이다. 행과 열을 더하면 line 번호가 나오고 그 line 전까지 나온 숫자에다가 행이나 열을 더하면 원하는 값이 나온다.

3. 정사각형을 대각선으로 나뉘는 두 개의 삼각형으로 잘라놓고 생각했을 때
아래 있는 삼각형은 위에 있는 삼각형과 대칭으로 생각할 수 있다.

// 아래 기본 제공된 코드를 수정 또는 삭제하고 본인이 코드를 사용하셔도 됩니다.
#include <stdio.h>
int N;
 double room_number(int x, int y) {
  int lineNum = x + y - 1;
  double result;
  if (lineNum > N) {
   x = N +1- x;
   y = N+1- y;
            lineNum=x+y-1;
   result = (lineNum)*(lineNum - 1) / 2;
   if (lineNum % 2 == 1) {
    result += y;
   }
   else {
    result += x;
   }
   return ((N*N) - result + 1);
  }
  else {
   result = (lineNum)*(lineNum - 1) / 2;
   if (lineNum % 2 == 1) {
    result += y;
   }
   else {
    result += x;
   }
   return result;
  }
 }
int main(void) {
    /* 아래 freopen 함수는 input.txt를 read only 형식으로 열고, 표준입력(키보드) 대신 input.txt 로 부터 읽어오겠다는 의미의 코드입니다.
    만약 본인 PC 에서 테스트 할 때는, 입력값을 input.txt에 저장한 후 freopen 함수를 사용하면
       그 아래에서 scanf 함수를 사용하여 표준입력 대신 input.txt 파일로 부터 입력값을 읽어 올 수 있습니다.
       또한, 본인 PC에서 freopen 함수를 사용하지 않고 표준입력을 사용하여 테스트하셔도 무방합니다.
    단, Codeground 시스템에서 "제출하기" 할 때에는 반드시 freopen 함수를 지우거나 주석(//) 처리 하셔야만 합니다. */
 // freopen("input.txt", "r", stdin);

 setbuf(stdout, NULL);

 int TC;
 int test_case;
int K, i, x, y;
  char ch;
  double count;
  scanf("%d", &TC);
  for (test_case = 1; test_case <= TC; test_case++) {
   // 이 부분에서 알고리즘 프로그램을 작성하십시오. 기본 제공된 코드를 수정 또는 삭제하고 본인이 코드를 사용하셔도 됩니다.
   scanf("%d %d\n", &N, &K);
   count = 1;
   x = 1, y = 1;
   for (i = 1; i <= K; i++) {
    scanf("%c", &ch);
    if (ch != 'D' && ch != 'U' && ch != 'R' && ch != 'L') printf("Direction must be one of character 'DURL'\n");
    if (ch == 'D') {
     x++;
     count += room_number(x, y);
    }
    if (ch == 'U') {
     x--;
     count += room_number(x, y);
    }
    if (ch == 'R') {
     y++;
     count += room_number(x, y);
    }
    if (ch == 'L') {
     y--;
     count += room_number(x, y);
    }
   }


   // 이 부분에서 정답을 출력하십시오.
   printf("Case #%d\n", test_case);
   printf("%.0lf\n", count);
  }

  return 0; // 정상종료 시 반드시 0을 리턴해야 합니다.
}