코딩코딩

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

프로그래머스 문제 2016년 과 유사한 문제 

2007년은 윤달이 아니며, 1/1일이 월요일로 시작 하는 것이 포인트 

string에 월요일부터 차례대로 모두 넣어줌 

x월이 1월 이상인 경우에 그 월의 요일을 모두 더해주고, 입력된 y일의 일수를 모두 더해서 7로 나눔

string에 한 번에 요일을 넣었기 때문에 일수의 합 %7 *3을 해주며 3칸씩해서 (요일)  답을 출력 

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

int main(void){
    int x,y;
    cin>>x>>y;
    int day[12] = { 31,28,31,30,31,30,31,31,30,31,30,31};
    string s = "MONTUEWEDTHUFRISATSUN";
    int sum = 0; 
    if(x>1){
      for(int i =0; i<x-1; i++){
        sum+=day[i];
      }
    }
    sum+= (y-1);
    string answer =s.substr(sum%7*3,3);
    cout<<answer<<"\n";
}

날짜 계산 로직,, 부시기 ,,,성공,,? 

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

완전탐색 문제 

행 기준/ 열 기준 모두 탐색을 해야함 

countCandy()

1. 행을 기준으로 옆에 요소와 탐색함 , 요소가 같은 경우에 temp의 개수를 늘려주고

아닐 경우 result값을 temp와 현 result의 최대 값으로 갱신,

마지막 for문을 나올 때 한번 더 max 값으로 갱신해줌

2. 열을 기준으로 아래 요소와 탐색  위와 같음 

main()

2차 배열이기 때문에 2중 for문을 돌며 각 행 기준 / 열 기준으로 옆 요소와 스왑했을 때

countCandy 함수로 자리가 변했을 때의 같은 요소의 최대값 개수를 리턴 받고 result에 갱신해줌

행, 열 기준으로 모든 요소 스왑하고 갱신된 max result값을 출력 

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

string board[51];
int n;

int countCandy(){
  int result = 1;
  for(int i=0; i<n; i++){
    int temp =1;
    for(int j=1; j<n; j++){
      if(board[i][j] == board[i][j-1]){
        temp++;
      }
      else{
        result = max(result,temp);
        temp = 1;
      }
    }
    result =max(result,temp);
  }

  for(int i=0; i<n; i++){
    int temp = 1; 
    for(int j=0; j<n-1; j++){
      if(board[j][i]== board[j+1][i]){
        temp ++;
      }
      else{
        result = max(result,temp);
        temp = 1;
      }
    }
    result = max(result,temp);
  }
  return result; 
}


int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>n;
  for(int i=0; i<n; i++){
    cin>>board[i];
  }
  int result =0;
  for(int i=0; i<n; i++){
    for(int j=0; j<n-1; j++){
      swap(board[i][j], board[i][j+1]);
      result = max(result,countCandy());
      swap(board[i][j], board[i][j+1]);

      swap(board[j][i], board[j+1][i]);
      result = max(result,countCandy());
      swap(board[j][i], board[j+1][i]);
    }
  }
  cout<<result<<"\n";
}

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

완전 탐색 문제 1

for문을 돌며 9명중 2명을 뺀 값의 합이 100인 경우에 요소를 모두 출력하도록

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

vector<int> vec;

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

  for(int i=0; i<9; i++){
    for(int j=0; j<9; j++){
      if(i==j) continue;
      if(sum-vec[i]-vec[j]==100){
        for(int k=0; k<9; k++){
          if(k!=i && k!=j){
            cout<<vec[k]<<"\n";
          }
        }
        return 0;
      }
    }
  }
 
 
}

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

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


int func(int num){
  int sum = num ;
  while(num){
    sum+=num%10;
    num /=10;
  }
  return sum;
}


int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin>>n;
  for(int i=1; i<n; i++){
    int sum = func(i);
    if(sum==n){
      cout<<i<<'\n';
      return 0;
    }
  }
  cout<<0<<"\n";
  
}

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

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

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

void dfs(int t, int p){
  if(t>n) return;
  sum = max(sum,p);
  for(int i=t; i<n; i++){
    dfs(i+vec[i].first, p+vec[i].second);
  }
}

int main(void){
  cin>>n;
  for(int i=0; i<n; i++){
    int t,p;
    cin>>t>>p;
    vec.push_back({t,p});
  }

  for(int i=0; i<n; i++){
    dfs(i+vec[i].first, vec[i].second);
  }
  cout<<sum<<"\n";
}

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

1~99는 모두 한수 그 이상일 때는 각 자리의 뺀 값을 비교하여 일치하는 경우에 한수라고

판별을 해준다. 

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

int n;

bool func(int num){
  int a = num/100;
  int b = (num-(100*a))/10;
  int c = num%10;

  if(num<100 || (a-b) == (b-c)) return true;
  return false;
}

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

  cout<<cnt<<"\n";  
}

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

요소를 인접 리스트 형식으로 받았으며 BFS로 탐색 !

바보 같은게 구현 방식이 맞았다고 생각했는데 자꾸 답이 1이 나와서 확인해보니

visited 배열을 bool 타입으로 선언해뒀었다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ아오 진짜 

10분이나 고민했네 바보,, 

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

int visited[101];
vector<int> vec[101];
int n,m;


int BFS(int s, int e){
  queue<int> q;
  q.push(s);
  
  while(!q.empty()){
    int cur =q.front();
    q.pop();
    if(cur == e){
      return visited[e];
    }
    for(int i=0; i<vec[cur].size(); i++){
      int nxt = vec[cur][i];
      if(visited[nxt]) continue;
      q.push(nxt);
      visited[nxt] = visited[cur]+1;
    }
  }
  return -1;
}

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>n;
  int x,y;
  cin>>x>>y;
  cin>>m;
  for(int i=0; i<m; i++){
    int a,b;
    cin>>a>>b;
    vec[a].push_back(b);
    vec[b].push_back(a);
  }
  cout<<BFS(x,y)<<"\n";
}

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

DFS 사용 

사이클 체크 하는 부분이 중요,, 

예제 처럼 4->7->6->4 사이클 일 때,

arr[4] = 7 /arr[7] = 6 /arr[6] = 4를 가지고 있다

dfs(4) 수행 , visited[4] = 1 (방문 표시) , arr[4] = 7 이기 때문에 7을 방문한 적 없으면

dfs(7) 수행, visited[7] = 1 , dfs(6) 수행 visited[6] = 1 ,  arr[6] = 4  / num = 6 nxt = 4 

visited[4] 는 이미 방문했기 때문에 else if 문 진입

cycle[4] = 0  for(int i=nxt ; i !=num ; i=arr[i]) 

i는 4,  i가 6가 될 때 까지 for문을 돌면서 개수를 세어준다 

4->7->6  /3개  / 6->4 개수도 세어준다 +1 

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

int t,n,cnt;
int arr[100001];
bool visited[100001];
bool cycle[100001];

void DFS(int num){
  visited[num] = 1;
  int nxt = arr[num];

  if(!visited[nxt]){
    DFS(nxt);
  }
  else if(!cycle[nxt]){
    for(int i=nxt ; i !=num ; i=arr[i]){
      cnt++;
    }
    cnt++;
  }
  cycle[num] = 1;
}

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>t;
  while(t--){
    cin>>n;
    memset(arr,0,sizeof(arr));
    memset(visited,0,sizeof(visited));
    memset(cycle,0,sizeof(cycle));

    for(int i=1; i<=n; i++){
      cin>>arr[i];
    }
    cnt = 0;
    for(int i=1; i<=n; i++){
      if(!visited[i]){
        DFS(i);
      }
    }
    cout<<n-cnt<<"\n";
  }
 
}

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

나는 아직 멀었다,, 왜이리 감이 안잡히는지,, ㅠㅠ 

물을 이동시킬 때 조건은 1. 한 물통이 비거나 2. 다른 물통이 가득 찰 때 이 두가지를 고려해야한다.

그리고 물을 이동시킬 수 있는 방법 

A->B 

A->C

B->A

B->C

C->A

C->B

6가지를 고려하여  각 통에 든 물의 양이 이동시키려는 통의 부피보다 클 때, 적을 때를 고려하여 

큐에 넣어주고, 조건대로 A 물통이 0일 때의 현재 물통 C 에 들어있는 물의 양을 벡터에 넣어준다

마지막으로 정렬하여 출력하면 끝,,,,,,,,

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

struct bottle{
  int a;
  int b;
  int c;
};
int A,B,C;

bool visited[202][202];

vector<int> bfs(){
  queue<bottle> q;
  q.push({0,0,C});
  vector<int> vec;
  while(!q.empty()){
    auto cur = q.front();
    q.pop();
    if(visited[cur.a][cur.b]) continue;

    visited[cur.a][cur.b] = 1;

    if(cur.a ==0)
      vec.push_back(cur.c);

    //a->b
    if(cur.a+cur.b > B)
    q.push({(cur.a+cur.b)-B,B,cur.c});
    else{
      q.push({0,cur.a+cur.b,cur.c});
    }

    //a->c
    if(cur.a+cur.c > C)
    q.push({(cur.a+cur.c)-C,cur.b,C});
    else{
      q.push({0,cur.b,cur.a+cur.c});
    }

    //b->a
    if(cur.a+cur.b > A)
    q.push({A,(cur.a+cur.b)-A,cur.c});
    else{
      q.push({cur.a+cur.b , 0, cur.c});
    }

    //b->c
    if(cur.c+cur.b > C)
    q.push({cur.a,(cur.c+cur.b)-C,C});
    else{
      q.push({cur.a,0,cur.c+cur.b});
    }

    //c->a
    if(cur.a+cur.c > A)
    q.push({A,cur.b, (cur.a+cur.c)-A});
    else{
      q.push({cur.a+cur.c , cur.b , 0});
    }

    //c->b
    if(cur.c+cur.b > B)
    q.push({cur.a,B,(cur.c+cur.b)-B});
    else{
      q.push({cur.a,cur.b+cur.c,0});
    }


  }
  return vec;
}

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>A>>B>>C;
  vector<int> result = bfs();
  sort(result.begin(),result.end());
  for(auto&i: result)
    cout<<i<<" "; 
}