훈감자 블로그

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

INT n;
vector<string> arr;
INT chk1, chk0;
void f(INT x, INT y, INT l)
{
  if(l==1)
  {
    if(arr[y][x] == '1')
    {
      cout << "1";
    }
    else{
      cout << "0";
    }
    return;
  }

  for(int i=y; i<y+l; i++)
    {
      for(int j=x; j<x+l; j++)
        {
          if(arr[i][j] == '0')  chk0=1;
          else  chk1=1;
        }
    }

  if(chk0 && chk1)
  {
    cout << "(";
    chk0 = chk1 = 0;
    f(x, y, l/2);
    chk0 = chk1 = 0;
    f(x+l/2, y, l/2);
    chk0 = chk1 = 0;
    f(x, y+l/2, l/2);
    chk0 = chk1 = 0;
    f(x+l/2, y+l/2, l/2);
    cout << ")";
  }
  else{
    if(chk0)  cout << "0";
    else  cout << "1";
  }
}

int main()
{
  cin >> n;

  for(int i=0; i<n; i++)
    {
      string str;

      cin >> str;
      arr.push_back(str);
    }

  f(0,0,n);
}

-분할 정복

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

INT n;
INT arr[129][129];
INT chk0, chk1; 
INT cnt0, cnt1;
void F(INT x, INT y, INT l)
{
  if(l == 1) {
    if(arr[y][x] == 1)  cnt1++;
    else  cnt0++;
    return;
  }
  for(int i=y; i<y+l; i++) {
    for(int j=x; j<x+l; j++) {
      if(arr[i][j] == 0)
        chk0 = 1;
      else
        chk1 = 1;
    }
  }

  if(chk0 && chk1)
  {
    chk0 = chk1 = 0;
    F(x, y, l/2);
    chk0 = chk1 = 0;
    F(x, y + l/2, l/2);
    chk0 = chk1 = 0;
    F(x + l/2, y, l/2);
    chk0 = chk1 = 0;
    F(x + l/2, y + l/2, l/2);
  }
  else{
    if(chk0) cnt0++;
    else  cnt1++;
  }

  
}

int main()
{
  cin >> n;

  for(int i=0; i<n; i++) {
    for(int j=0; j<n; j++) {
      cin >> arr[i][j];
    }
  }

  F(0,0,n);

  cout << cnt0 << endl << cnt1;
  
  return 0;
}

-분할정복

#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 <bits/stdc++.h>
using namespace std;
#define INT long long int 

INT n,m,vf;
bool chk[1010];
queue<INT> q;
bool visited[1010];
INT dis[1010];

void dfs(vector<INT> adj[], INT x)
{
  if(chk[x])  return;
  chk[x] = true;
  cout << x << " ";
  for(auto u: adj[x])
    {
      dfs(adj, u);
    }
}

void bfs(vector<INT> adj[], INT x)
{
  visited[x] = true;
  q.push(x);

  while(!q.empty())
    {
      INT s = q.front();
      q.pop();
      cout << s << " ";
      
      for(auto u: adj[s])
        {
          if(!visited[u])  
          {
            visited[u] = true;
            q.push(u);
          }
        }
    }
  
}

int main()
{
  cin >> n >> m >> vf;

  vector<INT> adj[n+1];
  for(int i=0; i<m; i++)
    {
      INT u = 0, v = 0;
      cin >> u >> v;
      adj[u].push_back(v);
      adj[v].push_back(u);
    }
  for(int i=1; i<n+1; i++)
    {
      sort(adj[i].begin(), adj[i].end()); 
    }
  
  dfs(adj,vf);
  cout << endl;
  bfs(adj,vf);

  return 0;
}

#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(반복문)

재귀로 dp하니 TLE 나서 for문으로 구현하니 통과..

For문 연습해야겠다..

ㅇ

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define MAX_ 987654321

typedef long long int INT;
INT n;
int main()
{
    cin >> n;

    vector<INT> v;
    v.resize(n+1);
    v[1] = 0;
    for(INT i=2; i<=n; i++)
    {
        v[i] = MAX_;
        if(i%2==0)
        {
            v[i] = min(v[i], v[i/2]+1);
        }
        if(i%3==0)
        {
            v[i] = min(v[i], v[i/3]+1);
        }
        if(i-1>0)
        {
            v[i] = min(v[i], v[i-1]+1);
        }
    }

    cout << v[n];
}

Dp 구현을 했더니 메모리 초과가 뜸 -> 귀찮아서 그냥 케이스 분류로 풂.

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long int INT;

INT n,ans;

int main()
{
    cin >> n;

    INT a = (n%5)%3==0?n/5+(n%5)/3:987654321;
    if(a==987654321)
    {
        INT i = n;
        INT d = 5;
        INT chk = 987654321;
        while(i-5>0)
        {
            i-=5;
            
            if(i%3 == 0)
            {
                chk = min(chk,(n-i)/5+i/3);
            }
        }
        if(chk!=987654321)  a = chk;
    }
    INT b = n%5==0?n/5:987654321;
    INT c = n%3==0?n/3:987654321;
    ans = min({a,b,c});
    INT p = ans!=987654321?ans:-1;

    cout << p;

    return 0;
}

정석대로 풀어봐야겠다..

#include <iostream>
#include <set>
#include <algorithm>
using namespace std;

typedef long long int INT;
set<INT> chk;

int main()
{
    for(INT i=1; i<10001; i++)
    {
        INT a=i;
        INT b=i;
        while(a/10 != 0)
        {
            b += a%10;
            a /= 10;
        }
        b += a;

        if(b<=10000)    chk.insert(b);
    }

    for(int i=1; i<10001; i++)
    {
        if(!chk.count(i))
        {
            cout << i << endl;
        }
    }

}

#include <bits/stdc++.h>
using namespace std;
#define INT unsigned long long int 
INT n,m,t,as;
INT ans;
INT memo[100][100];
INT f(INT x, INT y)
{
  if(x==0)  return 0;
  if(x==y || y==0)  return 1;
  if(memo[x][y])  return memo[x][y];
  memo[x][y] = f(x-1, y-1) + f(x-1, y);
  return memo[x][y];
}
int main()
{
  ios::sync_with_stdio(false);

  cin >> t;
  
  for(int j=0; j<t; j++)
  {
    as = 1;
n = m = 0; 
    cin >> n >> m;
    cout << f(m,n) << endl;
  }
  
return 0;
}