기본 콘텐츠로 건너뛰기

1022 : 소용돌이 예쁘게 출력하기 (Implementation) [C++]

어렵다..

막힌 이유는 시간과 메모리 때문.

처음에는 그냥 10001 * 10001개의 배열을 만들고 소용돌이를 만든 다음 접근하면 되겠지라는 생각에 여차저차해서 돌려보니 바로 메모리초과!

다음엔 4분의 1씩 생각해서 5000 * 5000을 만들고 돌려보니 시간 초과!

애초에 이 문제는 소용돌이를 만들어 놓으면 안된다..라는 생각이 들었고

규칙을 찾기 시작했다!

37
36
35
34
33
32
31
38
17
16
15
14
13
30
39
18
5
4
3
12
29
40
19
6
1
2
11
28
41
20
7
8
9
10
27
42
21
22
23
24
25
26
43
44
45
46
47
48
49


자 여기서 1로부터 각 8 방향의 값을 식으로 쓰기로 했는데 
늘어나는 값은 8이랑 연관이 있다.

예를 들어,

1의 ↖쪽에 있는 5는 1 + 4이고
5의 ↖쪽에 있는 17은 1 + 4 + 8 + 4이고
17의 ↖쪽에 있는 37은 1 + 4 + 8 + 4 + 8 + 4이다.

1의 ↗쪽에 있는 3은 1 + 2이고
3의 ↗쪽에 있는 13은 1 + 2 + 8 + 2이고
13의 ↗쪽에 있는 31은 1 + 2 + 8 + 2 + 8 + 2이다.

사실 DP를 이용하면 되게 점화식도 간단하게 나온다.

하지만 역시 메모리 문제때문에 DP는 불가능하고.. 각 행렬의 원소 값을 파악해 식을 써주

는 게 문제의 핵심이다.

8방향을 제외한 나머지의 값을 구하는 방법은?? 

8방향의 값에서 접근하면 된다.

예를 들어 5의 ↑쪽에 있는 16은 (-2,1)이고

16 = 17 - 1이다. 다르게 쓰면 16 = 17 + (-2 + 1)이다.

이와 같이 총 8개의 조건만 세운다면 원하는 크기의 소용돌이도 동적으로 만들 수 있다.

int Swirl::GetMax()
{
 int Max = 0;

 for (int Row = 0; Row < this->R_Size; Row++)
 {
  for (int Column = 0; Column < this->C_Size; Column++)
  {
   if (Max < this->Vector[Row][Column])
    Max = this->Vector[Row][Column];
  }
 }

 if (Max > 99999999)
  return 9;
 else if (Max > 9999999)
  return 8;
 else if (Max > 999999)
  return 7;
 else if (Max > 99999)
  return 6;
 else if (Max > 9999)
  return 5;
 else if (Max > 999)
  return 4;
 else if (Max > 99)
  return 3;
 else if (Max > 9)
  return 2;
 else
  return 1;
}

int Swirl::GetSum(int n)
{
 int i = n;
 int Sum = 0;
 while (i > 1)
 {
  Sum += i - 1;
  i--;
 }
 return Sum;
}

void Swirl::GetSwirl(int r1, int c1, int r2, int c2)
{
 int Tempc = c1;

 for (int i = 0;i < this->R_Size; i++)
 {
  for (int j = 0; j < this->C_Size;j++)
  {
   if (r1 == 0 && c1 == 0)
   {
    this->Vector[i][j] = 1;
   }
   if (r1 == 0 || c1 == 0)
   {
    if (c1 <0)
     this->Vector[i][j] = (8 * GetSum(abs(c1))) + (5 * abs(c1)) + 1;
    else if (c1 > 0)
     this->Vector[i][j] = (8 * GetSum(abs(c1))) + (1 * abs(c1)) + 1;
    else if (r1 <0)
     this->Vector[i][j] = (8 * GetSum(abs(r1))) + (3 * abs(r1)) + 1;
    else if (r1 > 0)
     this->Vector[i][j] = (8 * GetSum(abs(r1))) + (7 * abs(r1)) + 1;
   }
   else if (c1 < 0)
   {
    if (r1 < c1)
     this->Vector[i][j] = (8 * GetSum(abs(r1))) 
                    + (4 * abs(r1)) + (r1 - c1) + 1;
    else if(r1 > abs(c1))
     this->Vector[i][j] = (8 * GetSum(abs(r1)))
                    + (6 * abs(r1)) + (r1 + c1) + 1;
    else
     this->Vector[i][j] = (8 * GetSum(abs(c1)))
                    + (4 * abs(c1)) - (c1 - r1) + 1;
   }
   else if (c1 > 0)
   {
    if (r1 < 0)
    {
     if (abs(r1) > c1)
      this->Vector[i][j] = (8 * GetSum(abs(r1))) 
             + (2 * abs(r1)) - (c1 + r1) + 1;
     else if (abs(r1) <= c1)
      this->Vector[i][j] = (8 * GetSum(abs(c1))) 
             + (2 * abs(c1)) - (c1 + r1) + 1;
    }

    else if (r1 == c1)
     this->Vector[i][j] = (8 * GetSum(r1)) + (8 * r1) + 1;
    else if (r1 == c1 - 1)
     this->Vector[i][j] = (8 * GetSum(abs(c1 - 1))) 
                   + (8 * abs(c1 - 1)) + (c1 - r1) + 1;
    else if (r1 < c1)
     this->Vector[i][j] = (8 * GetSum(c1 - 1)) 
                   + (8 * abs(c1 - 1)) + (c1 - r1) + 1;
    else if (r1 > c1)
     this->Vector[i][j] = (8 * GetSum(r1)) + (8 * r1) - (r1 - c1) + 1;
   }
    
   c1++;
  }
  r1++;
  c1 = Tempc;
 }

 int MaxLength = this->GetMax();

 vector<vector<int>> CountVector;
 for (int i = 0; i < R_Size; i++)
 {
  vector<int> Temp;
  Temp.resize(C_Size);
  CountVector.push_back(Temp);
 }

 for (int Row = 0; Row < R_Size; Row++)
 {
  for (int Column = 0; Column < C_Size; Column++)
  {
   if (this->Vector[Row][Column] > 99999999)
    CountVector[Row][Column] = 9;
   else if (this->Vector[Row][Column] > 9999999)
    CountVector[Row][Column] = 8;
   else if (this->Vector[Row][Column] > 999999)
    CountVector[Row][Column] = 7;
   else if (this->Vector[Row][Column] > 99999)
    CountVector[Row][Column] = 6;
   else if (this->Vector[Row][Column] > 9999)
    CountVector[Row][Column] = 5;
   else if (this->Vector[Row][Column] > 999)
    CountVector[Row][Column] = 4;
   else if (this->Vector[Row][Column] > 99)
    CountVector[Row][Column] = 3;
   else if (this->Vector[Row][Column] > 9)
    CountVector[Row][Column] = 2;
   else
    CountVector[Row][Column] = 1;

   switch (MaxLength - CountVector[Row][Column])
   {
   case 1: cout << " "; break;
   case 2: cout << "  "; break;
   case 3: cout << "   "; break;
   case 4: cout << "    "; break;
   case 5: cout << "     "; break;
   case 6: cout << "      "; break;
   case 7: cout << "       "; break;
   case 8: cout << "        "; break;
   default: break;
   }

   cout << this->Vector[Row][Column] << " ";
  }
  cout << endl;
 }
}
<소스 코드>

예쁘게 출력하기 부분은 GetMax() 부분과 GetSwirl의 마지막 부분처럼 노가다를 하면 된다. 

*Source of the problem = https://www.acmicpc.net/problem/1022
*문제 출처 : BAEKJOON ONLINE JUDGE



라벨:

댓글

댓글 쓰기

이 블로그의 인기 게시물

1094 : 막대기 [C++]

# include < iostream > # include < vector > using namespace std ; int main ( ) { vector < int > Stick ; Stick . push_back ( 64 ) ; int Target ; cin > > Target ; int Last = 0 ; while ( true ) { if ( Target = = 64 ) break ; int Sum = 0 ; for ( int i = 0 ; i < Stick . size ( ) ; i + + ) Sum + = Stick [ i ] ; if ( Target = = Sum ) break ; else if ( Target < Sum ) { Stick [ Last ] / = 2 ; Sum = 0 ; for ( int i = 0 ; i < Stick . size ( ) ; i + + ) Sum + = Stick [ i ] ; if ( Target < = Sum ) continue ; else Stick . push_back ( Stick [ Last + + ] ) ; } } cout < < Stick . size ( ) ; ...
댓글 쓰기
자세한 내용 보기

2407 : 조합 (Dynamic Programming) [C++]

어려웠다. 문제를 풀면서 솔직히 이게 되려나?? 메모리 제한걸리려는게 아닌가 싶었는데 만들면서 최대한 메모리를 작게 만들었더니 맞았습니다! 주어진 입력 값은 최대 100인데, 입력값을 입력하면 오버플로우가 나므로 자릿수 배열을 만들어주어야 한다! 처음으로 한 생각은 재귀! (n == m || m == 0) 참이면 1 거짓이면 [n-1], [n]번째에 계속 접근하기 결과는 20이 넘어가면 엄청난 시간이 걸림. 두 번째 한 생각은 3차원 배열이었다. 2차원 배열에 또 배열을 만들어 자릿 수를 다 저장하려 했으나~ for문이 3개나 들어가서 시간이 엄청 오래걸렸음. 결국 2차원 배열이지만 3차원의 효과를 내게끔 선언하였다. 2차원배열이 원래이런 식이라면 1 11 121 1331 14641 내가 만든 배열은 111121133114641 즉 한 차원을 줄일 수 있었고, 각 원소에 대한 파스칼의 삼각형을 이용한 덧셈 공식은  그 줄의 자릿수 사이즈를 이용하여 전에 있는 줄에 접근하였다. DP 사용!! Answer[i] = Answer[i-Answer[i].size()] + Answer[i-Answer[i].size()+1] 그리고 저장한 자릿수들을 거꾸로 출력해주면 그것이 정답! Combination() : 각 줄의 번호만큼 자릿수를 가지는 벡터 생성, 계속 쓰는 Sum 벡터 생성 Increase() : 각 자릿수가 10이 넘어가면 올림을 해준다. GetSum() : 각 자릿수를 더해준다. GetAnswer() : DP, 올림, 출력  Combination :: Combination ( ) { this - > Sum . push_back ( 0 ) ; for ( int i = 1 ; i < = 101 ; i + + ) Sum . push_back ( S...
댓글 쓰기
자세한 내용 보기

11401 : 이항계수 3 (Dynamic Programming, Divide and Conquer) [C++]

1번, 2번 문제들과 확연히 차이나는 입력의 범위. 400만 ! DP를 사용해서 풀 수 없는 문제이다 . 하지만 DP가 쓰이긴 한다! 수학은 너무 어렵다. 곱셈의 역원을 공부해보다가 모르겠어서 도움을 구했다. 왜 곱셈의 역원을 구해야하는가? N! / (K! * (N-K)!) 에서 K! * (N-K)! 의 역원을 구해야 하기 때문! 곱셈의 역원을 구하는 정리인 페르마의 소정리를 이용하면 p가 1000000007 이지만 분할 정복을 이용한 제곱 수 계산 덕분에 logP 시간 소요. 분할 정복을 이용한 제곱 수 계산은 계속 써먹을 것 같아서 따로 올려놓았다. DP가 쓰이는 부분은 구해준 400만의 역원을 바탕으로 모든 역원을 구하는 부분이다. 그러므로 총 시간 소요는 O(N+LogP) long long BinomialCoefficient :: GetNum ( int N , int K ) { this - > Factorial [ 1 ] = 1 ; for ( int i = 2 ; i < = 4000000 ; i + + ) this - > Factorial [ i ] = ( this - > Factorial [ i - 1 ] * i ) % P ; this - > Invert [ 4000000 ] = this - > Pow_DC ( this - > Factorial [ 4000000 ] , P - 2 ) ; for ( int i = 4000000 - 1 ; i > 0 ; i - - ) this - > Invert [ i ] = ( this - > Invert [ i + 1 ] * ( i + 1 ) ) % P ; if ( N = = K | | K = ...
댓글 쓰기
자세한 내용 보기