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

 

10610번: 30

어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한

www.acmicpc.net

30의 배수

1. 끝 자리가 0

2. 각 자리 수 합이 3의 배수

 

-> 두 조건에 충족하는 경우에 내림차순 정렬 후 출력 

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


bool compare(char a, char b){
    return a>b;
}

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  string str;
  cin>>str;
  int sum=0;
  int flag = 0;
  for(int i=0; i<str.size(); i++){
    sum += (str[i]-'0');
    if(str[i]=='0')
      flag = 1;
  }

  if(flag == 1 && sum %3 ==0){
    sort(str.begin(), str.end(), compare);
    cout<<str<<"\n";
  }
  else{
    cout<<-1<<"\n";
  }

}
저작자표시 (새창열림)

'Algorithm > BOJ' 카테고리의 다른 글

[c++] 백준 2251 물통  (0) 2021.01.26
[c++] 백준 1744 수 묶기  (0) 2021.01.25
[c++] 백준 2110 공유기 설치  (0) 2021.01.22
[c++] 백준 2805 나무자르기  (0) 2021.01.22
[c++] 백준 10451 순열 사이클  (0) 2021.01.22

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

 

2110번: 공유기 설치

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가

www.acmicpc.net

이분 탐색 

좌표 값을 정렬하는 것이 포인트

high = 제일 먼 곳 - 제일 가까운 곳

low = 1

 

조건은 거리가 가장 멀면서 c개수 만큼의 공유기만 설치 가능하다는 것을 

함수로 만들어서 이분 탐색 중간에 조건으로 넣어주며 탐색 

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

int n,c;
long long arr[200002];

bool possible(int d){
  int cnt = 1;
  int pre = arr[0];
  for(int i=0; i<n; i++){
    if(arr[i]-pre >= d){
      cnt++;
      pre = arr[i];
    } 
  }
  if(cnt>=c) return true;
  else return false;
}

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>n>>c;
  for(int i=0; i<n; i++){
    cin>>arr[i];
  }
  sort(arr,arr+n);
  long long high = arr[n-1]-arr[0];
  long long low = 1;
  long long result =0;

  while(low<=high){
    long long mid = (low+high)/2;
    if(possible(mid)){
      result = max(result,mid);
      low = mid+1;
    }
    else{
      high = mid-1;
    }
  }
  cout<<result<<"\n";
}
저작자표시 (새창열림)

'Algorithm > BOJ' 카테고리의 다른 글

[c++] 백준 1744 수 묶기  (0) 2021.01.25
[c++] 백준 10610 30  (0) 2021.01.25
[c++] 백준 2805 나무자르기  (0) 2021.01.22
[c++] 백준 10451 순열 사이클  (0) 2021.01.22
[c++] 백준 10809 알파벳 찾기  (0) 2021.01.21

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

 

2805번: 나무 자르기

첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보

www.acmicpc.net

이분탐색  기본 해결 과정

1. 필요한 경우 정렬

2. high, low, mid 값 설정

3. 주어진 조건을 판별할 수 있도록 함수 구현

4. 이분 탐색 진행 

 

---> 백준 1654 문제와 유사 

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

int n,m;
long long arr[1000001];

bool possible(long long hight){
  long long sum =0; 
  for(int i=0; i<n; i++){
    if(arr[i]-hight < 0) continue;
    sum += arr[i]- hight; 
  }
  if(sum>=m) return true;
  else return false;
}

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>n>>m;
  long long high;
  for(int i=0; i<n; i++){
    cin>>arr[i];
    high = max(high,arr[i]);
  }
  long long low = 0;
  long long result =0; 
  while(low<=high){
    long long mid = (high+low)/2;
    if(possible(mid)){
      if(result<mid){
        result = mid;
      }
      low = mid+1;
    }
    else{
      high = mid-1;
    }
  }
  cout<<result<<"\n";
}
저작자표시 (새창열림)

'Algorithm > BOJ' 카테고리의 다른 글

[c++] 백준 10610 30  (0) 2021.01.25
[c++] 백준 2110 공유기 설치  (0) 2021.01.22
[c++] 백준 10451 순열 사이클  (0) 2021.01.22
[c++] 백준 10809 알파벳 찾기  (0) 2021.01.21
[c++] 백준 11053/ 11722 가장 긴 증가하는/감소하는 부분 수열  (0) 2021.01.21

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

 

10451번: 순열 사이클

1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\  3

www.acmicpc.net

dfs 사용 

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

int t;
vector<int> vec[1002];
bool visited[1002]; 

void dfs(int n){
  if(visited[n]) return;
  visited[n] = 1;
  for(int i=0; i<vec[n].size(); i++){
    int nxt = vec[n][i];
    dfs(nxt);
  }
}

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>t;
  while(t--){
    int n;
    cin>>n;
    memset(vec,0,sizeof(vec));
    memset(visited,0,sizeof(visited));
    for(int i=0; i<n; i++){
      int num; 
      cin>>num;
      vec[i+1].push_back(num);
    }
    int cnt = 0;
    for(int i=1; i<=n; i++){
      if(!visited[i]){
        dfs(i);
        cnt++;
      }
    }
    cout<<cnt<<"\n";

  }
  
}
저작자표시 (새창열림)

'Algorithm > BOJ' 카테고리의 다른 글

[c++] 백준 2110 공유기 설치  (0) 2021.01.22
[c++] 백준 2805 나무자르기  (0) 2021.01.22
[c++] 백준 10809 알파벳 찾기  (0) 2021.01.21
[c++] 백준 11053/ 11722 가장 긴 증가하는/감소하는 부분 수열  (0) 2021.01.21
[c++] 백준 11055 가장 큰 증가 부분 수열  (0) 2021.01.21

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

 

10809번: 알파벳 찾기

각각의 알파벳에 대해서, a가 처음 등장하는 위치, b가 처음 등장하는 위치, ... z가 처음 등장하는 위치를 공백으로 구분해서 출력한다. 만약, 어떤 알파벳이 단어에 포함되어 있지 않다면 -1을 출

www.acmicpc.net

stl의 find라는 엄청난 함수 사용 

stl 공부좀 해야겠다 뻘짓할 뻔 했네,, 

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

int fre[26];

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  string str;
  cin>>str;
  fill(fre,fre+26,-1);
  string a = "abcdefghijklmnopqrstuvwxyz";

  for(int i=0; i<a.size(); i++){
    if(str.find(i)){
      fre[i] = str.find(a[i]);
    }
  }
  for(int i=0; i<26; i++){
    cout<<fre[i]<<" ";
  }
}
저작자표시 (새창열림)

'Algorithm > BOJ' 카테고리의 다른 글

[c++] 백준 2805 나무자르기  (0) 2021.01.22
[c++] 백준 10451 순열 사이클  (0) 2021.01.22
[c++] 백준 11053/ 11722 가장 긴 증가하는/감소하는 부분 수열  (0) 2021.01.21
[c++] 백준 11055 가장 큰 증가 부분 수열  (0) 2021.01.21
[c++] 백준 11057 오르막 수  (0) 2021.01.21

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

 

 

11053번: 가장 긴 증가하는 부분 수열

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이

www.acmicpc.net

1번과 2번 문제 아주 유사한 문제로 조건문내의 조건만 바꿔주면 된다.

 

 

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


int n;
int d[1001];
int arr[1001];
int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>n;
  for(int i=0; i<n; i++){
    cin>>arr[i];
  }
  int sum = 0;
  for(int i=0; i<n; i++){
    d[i] = 1;
    for(int j = 0; j<i; j++){
      if(arr[i]>arr[j]){
        d[i] = max(d[i], d[j]+1);
      }
    }
    sum = max(sum,d[i]);
  }
  cout<<sum<<"\n";
 
}

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

 

11722번: 가장 긴 감소하는 부분 수열

수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} 

www.acmicpc.net

 

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


int n;
int d[1001];
int arr[1001];
int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>n;
  for(int i=0; i<n; i++){
    cin>>arr[i];
  }
  int sum = 0;
  for(int i=0; i<n; i++){
    d[i] = 1;
    for(int j = 0; j<i; j++){
      if(arr[i]<arr[j]){
        d[i] = max(d[i], d[j]+1);
      }
    }
    sum = max(sum,d[i]);
  }
  cout<<sum<<"\n";
}
저작자표시 (새창열림)

'Algorithm > BOJ' 카테고리의 다른 글

[c++] 백준 10451 순열 사이클  (0) 2021.01.22
[c++] 백준 10809 알파벳 찾기  (0) 2021.01.21
[c++] 백준 11055 가장 큰 증가 부분 수열  (0) 2021.01.21
[c++] 백준 11057 오르막 수  (0) 2021.01.21
[c++] 백준 10844 쉬운 계단 수  (0) 2021.01.21

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

 

11055번: 가장 큰 증가 부분 수열

수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수

www.acmicpc.net

갈 길이 멀다 ~ 

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


int n;
int d[1001];
int arr[1001];
int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>n;
  for(int i=0; i<n; i++){
    cin>>arr[i];
  }
  int sum = 0;
  for(int i=0; i<n; i++){
    d[i] = arr[i];
    for(int j = 0; j<i; j++){
      if(arr[i]>arr[j]){
        d[i] = max(d[i], d[j]+ arr[i]);
      }
    }
    sum = max(sum,d[i]);
  }
  cout<<sum<<"\n";
}
저작자표시 (새창열림)

'Algorithm > BOJ' 카테고리의 다른 글

[c++] 백준 10809 알파벳 찾기  (0) 2021.01.21
[c++] 백준 11053/ 11722 가장 긴 증가하는/감소하는 부분 수열  (0) 2021.01.21
[c++] 백준 11057 오르막 수  (0) 2021.01.21
[c++] 백준 10844 쉬운 계단 수  (0) 2021.01.21
[c++] 백준 4963 섬의 개수  (0) 2021.01.19

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

 

11057번: 오르막 수

오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수

www.acmicpc.net

dp

f[2][k] = f[1][0] +  f[1][1] +  f[1][2]+...+ f[1][k] 

f[n][k] = f[n-1][0] + f[n-1][1] +  f[n-1][2] +... +  f[n-1][k] 

 

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

#define M 10007;
int n;
int d[1001][10];

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>n;
  
 for(int i=0; i<10; i++){
    d[1][i] = 1;
 }
 for(int i=2; i<=n; i++){
   for(int j=0; j<10; j++){
      for(int k = j; k>=0; k--){
        d[i][j]+= d[i-1][k] %M;
      }
     }
   }
 
 int ans =0;
 for(int i=0; i<10; i++){
   ans += d[n][i]%M;
 }
 cout<<ans%M;  
}
저작자표시 (새창열림)

'Algorithm > BOJ' 카테고리의 다른 글

[c++] 백준 11053/ 11722 가장 긴 증가하는/감소하는 부분 수열  (0) 2021.01.21
[c++] 백준 11055 가장 큰 증가 부분 수열  (0) 2021.01.21
[c++] 백준 10844 쉬운 계단 수  (0) 2021.01.21
[c++] 백준 4963 섬의 개수  (0) 2021.01.19
[c++] 백준 11725 트리의 부모 찾기  (0) 2021.01.18

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

 

10844번: 쉬운 계단 수

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

www.acmicpc.net

 

dp 문제 

각 계단 수는 이전 마지막 숫자에 영향을 받는다.

0일 때 / 9일 때/ 1~8일 때 각 나눠서 점화식을 세우기 

마지막 수가 1~8 일 때 , 다음 올 수 있는 수는 그 수의 X +1 or X-1만 가능 

 

ans 변수를 초기화 해주는 걸 깜빡해서 헛고생좀 했다 ,, ㅇ<-<

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

#define M 1000000000;
int n;
int d[101][10];

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin>>n;
  
 for(int i=1; i<10; i++){
    d[1][i] = 1;
 }
 for(int i=2; i<=n; i++){
   for(int j=0; j<10; j++){
     if(j == 0) d[i][0] = d[i-1][1];
     else if(j == 9) d[i][9] = d[i-1][8];
     else{
       d[i][j] = (d[i-1][j-1] + d[i-1][j+1])%M;
     }
   }
 }
 int ans =0;
 for(int i=0; i<10; i++){
   ans = (ans+d[n][i])%M;
 }
 cout<<ans%M;  
}
저작자표시 (새창열림)

'Algorithm > BOJ' 카테고리의 다른 글

[c++] 백준 11055 가장 큰 증가 부분 수열  (0) 2021.01.21
[c++] 백준 11057 오르막 수  (0) 2021.01.21
[c++] 백준 4963 섬의 개수  (0) 2021.01.19
[c++] 백준 11725 트리의 부모 찾기  (0) 2021.01.18
[c++] 백준 7785 회사에 있는 사람  (0) 2021.01.18

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

 

4963번: 섬의 개수

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도

www.acmicpc.net

dfs 사용, 가로세로+ 대각선 까지 고려하여 탐색 

힘들다 힘들어 ~ 

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


int n,m;
int arr[52][52];
bool visited[52][52];
int cnt;

int dx[8] ={-1,0,1,-1,1,-1,0,1};
int dy[8] = {1,1,1,0,0,-1,-1,-1};

void dfs(int x, int y){
  for(int i=0; i<8; i++){
    int nx = x+dx[i];
    int ny = y+dy[i];

    if(nx <0 || nx>=m || ny<0 || ny>=n ) continue;
    if(arr[nx][ny] == 0 || visited[nx][ny] == 1 ) continue;
    visited[nx][ny] = 1;
    dfs(nx,ny);
  }

}


int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  while(1){
    cin>>n>>m;
    if(n==0 && m==0) break;

    memset(arr,0,sizeof(arr));
    memset(visited, 0, sizeof(visited));

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

    for(int i=0; i<m; i++){
      for(int j=0; j<n; j++){
        if(arr[i][j] == 1 && visited[i][j] == 0){
          cnt ++;
          dfs(i,j);
        }
      }
    }
    cout<<cnt<<'\n';
    cnt =0;
  }
}
저작자표시 (새창열림)

'Algorithm > BOJ' 카테고리의 다른 글

[c++] 백준 11057 오르막 수  (0) 2021.01.21
[c++] 백준 10844 쉬운 계단 수  (0) 2021.01.21
[c++] 백준 11725 트리의 부모 찾기  (0) 2021.01.18
[c++] 백준 7785 회사에 있는 사람  (0) 2021.01.18
[c++] 백준 11724 연결 요소의 개수  (0) 2021.01.17

+ Recent posts

티스토리툴바