훈감자 블로그

#include <bits/stdc++.h>
using namespace std;
#define INT long long int 

INT n;

void f(INT x, INT y, INT num)
{
  if((x/num)%3 == 1 && (y/num)%3 == 1) {
    cout << ' ';
  }
  else{
    if(num/3 == 0)  cout << "*";
    else  f(x,y,num/3);
  }
}

int main()
{
  cin >> n;
  for(INT i=0; i<n; i++) {
    for(INT j=0; j<n; j++) {
      f(i,j,n);
    }
    cout << "\n";
  }
}


-분할정복

#include <iostream>
#include <queue>
#include <functional>
#define INT long long int 
using namespace std;

INT n;

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    priority_queue<INT, vector<INT>, greater<INT> > p;
    priority_queue<INT> q;

    cin >> n;

    for(int i=0; i<n; i++)
    {
        INT m = 0;
        cin >> m;

        if(q.empty())
        {
            q.push(m);
        }
        else{
            if(p.size() + 1 == q.size() || p.size() + 2 == q.size())
            {
                p.push(m);
                if(q.top() > p.top())
                {
                    INT qq = q.top();
                    INT pp = p.top();
                    q.pop();
                    p.pop();
                    q.push(pp);
                    p.push(qq);
                }
            }
            else{
                q.push(m);
                if(q.top() > p.top())
                {
                    INT qq = q.top();
                    INT pp = p.top();
                    q.pop();
                    p.pop();
                    q.push(pp);
                    p.push(qq);
                }
            }
        }
        cout << q.top() << "\n";
    }

    return 0;
}

-우선순위 큐 

#include <bits/stdc++.h>
#define INT long long int 
using namespace std;

INT n,k;
INT w[110], v[110];
INT dp[110][100010];

int main()
{
  cin >> n >> k;
  
  for(int i=1; i<n+1; i++)
    {
      cin >> w[i] >> v[i];
    }

  for(int i=1; i<k+1; i++)
    {
      for(int j=1; j<n+1; j++)
        {
          if(w[j] > i)
          {
            dp[j][i] = dp[j-1][i];
          }
          else{
            dp[j][i] = max(dp[j-1][i-w[j]] + v[j], dp[j-1][i]);
          }
        }
    }

  cout << dp[n][k];


  return 0;
}

- dp(반복문)