기본 콘텐츠로 건너뛰기

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



라벨:

댓글

댓글 쓰기

이 블로그의 인기 게시물

11004 : K번째 수 [C++]

# include < iostream > # include < cstdio > # include < algorithm > int main ( ) { int * Number = new int [ 5000000 ] ; int N , K ; scanf ( " %d %d " , & N , & K ) ; for ( int i = 0 ; i < N ; i + + ) scanf ( " %d " , Number [ i ] ) ; std :: sort ( Number , Number + N ) ; printf ( " %d " , Number [ K - 1 ] ) ; return 0 ; }
댓글 쓰기
자세한 내용 보기

1149 : RGB Street Coloring (Dynamic Programming) [C,C++]

The key to this problem lies in understanding the principles. Let me explain the algorithm to solve the problem by using DP. First, you need the same storage space like input data's size. When you draw any color of the nth house, the space will contain the minimum value. If you paint the red in the second house, this value is sum of blue or green of the first house.  You must use DP because you must use the previous value.  Of course, you can also use the recursive algorithm to solve it. But if it gets bigger, it will take a lot of time.  If you paint the red in the nth house in the same way, you should add the lower value of the blue and green of the n-1th house.  Therefore, the minimum value can be found in the value of the storage space (n-1) index. <pesudo code> *Source of the problem =  https://www.acmicpc.net/problem/1149 *문제 출처 : BAEKJOON ONLINE JUDGE
댓글 쓰기
자세한 내용 보기

11478 : 서로 다른 부분 문자열의 개수 (미제) [C++]

# include < iostream > # include < vector > # include < string > using namespace std ; int main ( ) { string sInput ; getline ( cin , sInput , '\n' ) ; int Time = 1 ; int Count = 0 ; vector < string > Storage ; for ( int i = 0 ; i < sInput . size ( ) ; i + + ) { for ( int j = 0 ; ( j + Time - 1 ) < sInput . size ( ) ; j + + ) Storage . push_back ( sInput . substr ( j , Time ) ) ; Time + + ; } bool * Visited = new bool [ Storage . size ( ) * sizeof ( bool ) ] ; for ( int i = 0 ; i < Storage . size ( ) ; i + + ) { Visited [ i ] = true ; for ( int j = 0 ; j < Storage . size ( ) ; j + + ) { if ( i ! = j & & Storage [ i ] = = Storage [ j ] ) { Visited [ i ] = false ; Visited [ j ] = true ; break ; } } } for ( int i = 0 ; i < Storage . size ( ) ; i + + ) if ( Visited [ i ] ) Count ...
댓글 쓰기
자세한 내용 보기