코딩코딩

https://www.acmicpc.net/problem/1946

문제를 제대로 안읽어서 몇분을 헤맨건지,, 

처음엔 서류/면접 순위를 점수로 생각해서 오름차순이 아닌 내림차순 정렬로 풀어서 틀리고..

습관처럼 지원자 숫자와 벡터를 전역변수로 선언해서 계속 틀렸습니다 라는 결과가 나왔다 ㅠㅠ

이 멍충이 ㅠㅠ  문제 제대로 읽자 !!!!! ᕕ( ᐛ )ᕗ

#include <bits/stdc++.h>
using namespace std;

int t;

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>t;
  while(t--){
      int n;
      cin>>n;
      vector<pair<int,int>> vec;
      for(int i=0; i<n; i++){
          int x,y;
          cin>>x>>y;
          vec.push_back({x,y});
      }
      sort(vec.begin(), vec.end());
      
      int ans = 1;
      int temp = vec[0].second;
      for(int i=1; i<n; i++){
          if(temp > vec[i].second){
              ans ++;
              temp = vec[i].second;
          }
      }
      cout<<ans<<'\n';
  }
}

https://www.acmicpc.net/problem/1931

- 회의가 빨리 끝나는 회의로 선택

- 끝나는 시간이 같다면 시작 시간이 빠른 회의 선택

시작 시간과 끝나는 시간을 바꿔서 넣으며 정렬 진행 

=> 다음 선택될 회의는 현 시간 과 시작시간이 같거나 이상이어야 한다

#include <bits/stdc++.h>
using namespace std;


vector<pair<int,int>> vec;
int n;

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>n;
  for(int i=0; i<n; i++){
    int s,e;
    cin>>s>>e;
    vec.push_back({e,s});
    
  }
  sort(vec.begin(), vec.end());

  int num = 0;
  int t = 0;

  for(int i=0; i<n; i++){
    if(t > vec[i].second) continue;
    num++;
    t = vec[i].first;
  }
  cout<<num;
}

https://www.acmicpc.net/problem/11047

DP 하기 싫어서 그리디로 도망 

#include <bits/stdc++.h>
using namespace std;

int a[10];
int n,k;

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>n>>k;
  for(int i=0; i<n; i++){
    cin>>a[i];
  }
  int num =0;
  for(int i=n-1; i>=0; i--){
    int t = k/a[i];
    num += t;
    k -= a[i]*t;
  }
  cout << num;
}

https://www.acmicpc.net/problem/2156

DP !!!!  

n번째 포도주를 마시지 않을 때 d[n-1]

n번째 포도주 마시고, n-1번째 마시지 않을 때 d[n-2] + s[n]

n번째 포도주 마시고, n-1 번째도 마실 때  (n-2까지 마시면 연속 3번이라 조건 x) 

                                         d[n-3] + s[n] + s[n-1] 

0번 연속 마실때, 1번 연속 , 2번 연속 총 3가지 모든 요소 중에 최댓값을 출력

감이 잡히는거 같으면서도,, 모르겠네,,,,,,, ㅇ<-< 

#include <bits/stdc++.h>
using namespace std;

int d[10005];
int s[10005];
int n;


int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>n;
  for(int i=1; i<=n; i++){
    cin>>s[i];
  }
  d[0] = 0;
  d[1] = s[1];
  d[2] = s[1]+s[2];

  for(int i=3; i<=n; i++){
    d[i] = max(max(d[i-1], d[i-2]+s[i]),d[i-3]+s[i]+s[i-1]);
  }
  cout<<d[n];
  
}

https://www.acmicpc.net/problem/2193

DP.........

#include <bits/stdc++.h>
using namespace std;

long long d[91][2];

int n,m;
int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>n;
  d[1][0] = 0;
  d[1][1] = 1;
  for(int i=2; i<=n; i++){
    d[i][0] = d[i-1][0] + d[i-2][0];
    d[i][1] = d[i-1][1] + d[i-2][1];
  }
  cout<<d[n][0]+d[n][1];
  
}

https://www.acmicpc.net/problem/9095

오늘도 DP 

#include <bits/stdc++.h>
using namespace std;

int n;
int d[300];

void func(int num){
  d[1] = 1;
  d[2] = 2;
  d[3] = 4;
  for(int i=4; i<=num; i++){
    d[i] = d[i-1]+d[i-2]+d[i-3];
  }
  cout<<d[num]<<'\n';
}

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>n;
  for(int i=0; i<n; i++){
    int nu;
    cin>>nu;
    func(nu);
  }
  
}

https://www.acmicpc.net/problem/11727

DP.....ㅇ<-<

#include <bits/stdc++.h>
using namespace std;

int n;
int d[10005];

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>n;

  d[1] = 1;
  d[2] = 3;
  d[3] = 5;
  d[4] = 11;

  for(int i=5; i<=n; i++)
    d[i] = (d[i-1]+d[i-2]*2)%10007;
  
  cout<<d[n];
  
}

https://www.acmicpc.net/problem/11726

DP!!!!!

#include <bits/stdc++.h>
using namespace std;


int n;
int d[10005];

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>n;
  
  d[1] = 1;
  d[2] = 2;
  d[3] = 3;

  for(int i=4; i<=n; i++){
    d[i] = (d[i-1]+d[i-2])%10007;
  }

  cout<<d[n];
}

https://www.acmicpc.net/problem/1149

DP

#include <bits/stdc++.h>
using namespace std;

int n;
int d[1005][3];
int s[1005][3];

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>n;
  
  for(int i=0; i<n; i++){
      cin>>s[i][0]>>s[i][1]>>s[i][2];
  }
  d[0][0] =s[0][0];
  d[0][1] =s[0][1];
  d[0][2] =s[0][2];

  for(int i=1; i<n; i++){
      d[i][0] = min(d[i-1][1], d[i-1][2])+s[i][0];
      d[i][1] = min(d[i-1][0], d[i-1][2])+s[i][1];
      d[i][2] = min(d[i-1][0], d[i-1][1])+s[i][2];
  }

cout<<min(min(d[n-1][0],d[n-1][1]),d[n-1][2]);
  
}

https://www.acmicpc.net/problem/2579

DP는 역시 어려워 

점화식 파악하는게 가장 중요 포인트 

계단을 밟지 않는 것을 기준으로 진행하였기 때문에

결과 : 모든 계단의 합 - 밟지 않은 계단의 총 합의 최소값 

#include <bits/stdc++.h>
using namespace std;


int n;
int d[305];
int s[305];

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>n;
  int num =0;
  for(int i=0; i<n; i++){
      cin>>s[i];
      num += s[i];
  }
  if(n<=2){
      cout<<n;
      return 0;
  }
  d[0] = s[0];
  d[1] = s[1];
  d[2] = s[2];
  
  for(int i=3; i< n-1 ; i++){
      d[i] = min(d[i-2], d[i-3])+s[i];
  }

  cout<<num-min(d[n-2],d[n-3]);
}

이번주 내내 DP만 판다............ㅇ<-<