시작 수 666부터 1씩 더해가면서 검사한다. 
숫자가 증가할 때마다 to_string(숫자) 함수로 문자열 변환을 해준다. 
string 에서 substring 의 포함여부를 검색하는데 find() 함수를 썼다. 
 
문자열“666”이 포함되면 0을 포함한 인덱스를 반환해준다.
포함되지 않으면, 엄청나게 큰 수를 반환한다. 
이 때, -1 보다는 string::npos 를 써서 검사하자. 
 
#include <bits/stdc++.h>
using namespace std;

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

  cin >> n;

  string target = "666";
  int num = 665;
  int count = 0;

  while(++num){
    s = to_string(num); // int to string
    if(s.find(target) != string::npos) ++count; // 타겟이 존재한다면 카운팅한다.
    if(count == n) break;
  }
  cout << num;
  return 0;
}
 
728x90
저작자표시 비영리 변경금지

'알고리즘 > 백준' 카테고리의 다른 글

마인크래프트 백준 18111번 c++  (0) 2022.02.14
방 번호 백준 1475번 c++  (0) 2022.02.14
랜선 자르기 백준 1652번 c++  (0) 2022.02.14
카드 백준 11652번 c++  (0) 2022.02.13
쇠막대기 백준 10799번 c++  (0) 2022.02.13
 
중요한 이분탐색 문제. 
 
서로다른 길이를 a로 나눠서 n개 이상의 랜선을 만들어야 한다. 
a로 나눠야 하는 최소 길이는 1이다. 
최대 길이는 주어진 랜선 중에 가장 긴 랜선이다. 
 
1부터 최대 길이까지 나눠보는데, 이분 탐색을 이용한다. 
기본은 (low + high ) / 2 = mid 임을 이용한다. 
mid 길이로 모든 랜선을 나눠서 몇 개 count 의 랜선이 나오는지 센다. 
 
만약 결과count가 목표개수 n 보다 적게 나온다면, 더 짧은 길이로 나눠야 더 많은 개수가 나올 것이다. 
따라서  count < n 이라면,  최대 길이 end = mid -1 로 줄인다. 
 
count가 n개와 같거나 크다면, start = mid +1 로 늘려서 더 길게 나눠도 n개 이상임을 만족하는지 탐색한다. 
 
#include <bits/stdc++.h>
using namespace std;

int k, n; // 가지고있는 랜선 개수, 필요한 개수
int maxlen;
int line[10002];
long long mid, high, low;

int count(int t){
  int cnt = 0 ;
  for(int i = 0; i < k; i++) cnt += (line[i] / t);
  return cnt;
}

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

  cin >> k >> n;

  for(int i = 0; i < k; i++){
    cin >> line[i];
    if(maxlen < line[i]) maxlen = line[i];
  }

  high = maxlen, low = 1; //최대길이, 최소길이
  long long answer = 0;

  while(low <= high){ /* 이분탐색 */
    mid = (low + high)/ 2;
    int cnt = count(mid); // 개수 세기 

    if(cnt >= n) {
      low = mid + 1;
      if(answer < mid) answer = mid;
    }
    else {
      high = mid - 1;
    }
  }

  cout << answer;
  return 0;
}
 
 
#include <bits/stdc++.h>
using namespace std;

int k, n;
long long answer, maxlen;
long long v[10002];

int count(int temp){
  int cnt = 0;
  for(int i = 0; i < k; i++) cnt += (v[i] / temp);
  return cnt;
}

void binary(long long start, long long end){
  if(start > end) return;

  long long mid = (start + end)/2;
  long long cnt = count(mid); 개수 세기 

  if(cnt >= n){
    answer = max(answer, mid);
    binary(mid + 1, end);
  }
  else{
    binary(start, mid - 1);
  }
}
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> k >> n;

  for(int i = 0; i < k; i++){
    cin >> v[i];
    maxlen = max(maxlen, v[i]);
  }

  binary(1, maxlen);
  cout << answer;
  return 0;
}
 
 
728x90
저작자표시 비영리 변경금지

'알고리즘 > 백준' 카테고리의 다른 글

방 번호 백준 1475번 c++  (0) 2022.02.14
영화감독 숌 백준 1436번 c++  (0) 2022.02.14
카드 백준 11652번 c++  (0) 2022.02.13
쇠막대기 백준 10799번 c++  (0) 2022.02.13
괄호 백준 9012번 c++  (0) 2022.02.13
같은 숫자를 가진 카드가 몇개씩 있는지 세야 한다. 
 
/** 카드
 
 */
#include <bits/stdc++.h>
using namespace std;

int n, maxnum;
long long num, answer;
map<long long, int> card_map; //<숫자, 개수>

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

  cin >> n;
  while(n--){
    cin >> num;
    card_map[num]++;
  }

  for(auto n : card_map){
    if(n.second > maxnum) {
      maxnum = n.second;
      answer = n.first;
    }
  }
  cout << answer;

  return 0;
}
 
숫자 마다의 개수를 저장해야 하니까 map 으로 입력받았다. <숫자, 카드의 개수> 
 
최대 카드 개수가 10만 이하여서 한번 반복문으로 순회했다. 
 
개수가 가장 많은 것을 만나면 maxnum으로 저장하고, 그 숫자를 answer에 저장했다. 
728x90
저작자표시 비영리 변경금지

'알고리즘 > 백준' 카테고리의 다른 글

영화감독 숌 백준 1436번 c++  (0) 2022.02.14
랜선 자르기 백준 1652번 c++  (0) 2022.02.14
쇠막대기 백준 10799번 c++  (0) 2022.02.13
괄호 백준 9012번 c++  (0) 2022.02.13
좋은 단어 백준 3986번 c++ (두번째 풀기)  (0) 2022.02.11

문제링크

 

스택을 이용해 풀었다. 

( ) 이렇게 레이저를 쏠 때 스택에 아무것도 없으면 막대 조각이 생성되지 않는다. 

 

괄호가 레이저를 쐈는지 식별하려면?

지금 문자열이  ) 이고, 이전이 ( 인지 확인하면 된다. 

 

 ( 는 막대가 시작하는 지점이다. 

 

( ( ) ) 길이 1의 막대에 레이저 1번 쏘면, 길이 1 + 현재 스택길이 1 ==> 총 조각 2개가 생성된다. 

( ( ( ) ) ) 길이 2의 막대에 레이저 1번 쏘면, 길이 2 + 현재 스택길이 2 ==> 총 4개가 생성된다. 

 

) 는 막대가 끝나는 지점이니까 answer 에 +1을 한다. 

 

맞았습니다 코드링크

/** 쇠막대기
 https://www.acmicpc.net/problem/10799
 http://boj.kr/4fcfe35ad9a14a5898bf22af9c5f25c9
 */

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

long long answer;
string input;

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

  cin >> input;

  stack<char> st;
  int len = input.length();
  for(int i = 0; i < len; i++){

    if(input[i] == '(') {
      st.push(input['i']);
    }
    else if(input[i-1] == '(' && input[i] == ')'){ // 레이저
      st.pop();
      answer += st.size();
    }else { // 막대의 마지막 꼬다리
      answer++;
      st.pop();
    }
  }

  cout << answer;
  return 0;
}
728x90
저작자표시 비영리 변경금지

'알고리즘 > 백준' 카테고리의 다른 글

랜선 자르기 백준 1652번 c++  (0) 2022.02.14
카드 백준 11652번 c++  (0) 2022.02.13
괄호 백준 9012번 c++  (0) 2022.02.13
좋은 단어 백준 3986번 c++ (두번째 풀기)  (0) 2022.02.11
Hasing 백준 15829번 c++  (0) 2022.02.11
 
스택을 이용한 기본 문제였다. 
항상 top()을 접근하기 전에 스택이 empty() 인지를 확인해야 한다! (이걸 자주 빠뜨렸었다. )
( 이면 푸시한다. 
) 가 나오면, 현재 스택이 비어있지 않은지 확인하고, top() 이 ( 인지 확인한다. 
( 과 )는 짝이 맞는 괄호이기 때문에, 현재 top() 인 (를 팝 한다. 
오늘은 한 번에 맞았다. 
 
 
/** 괄호
 https://www.acmicpc.net/problem/9012
 http://boj.kr/ac1a8f71cfbe4c62abbc1aa710778283
 */
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

int t;
string input;

bool check(string s){
  stack<char> st;
  for(auto i : s){
    if(i == '(') st.push('(');
    else if(!st.empty() && st.top() == '('){
      st.pop();
    }else return false;
  }

  if(st.empty()) return true;
  else return false;
}
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> t;

  while(t--){
    cin >> input;
    if(check(input)) cout << "YES" << endl;
    else cout << "NO" << endl;
  }

  return 0;
}
728x90
저작자표시 비영리 변경금지

'알고리즘 > 백준' 카테고리의 다른 글

카드 백준 11652번 c++  (0) 2022.02.13
쇠막대기 백준 10799번 c++  (0) 2022.02.13
좋은 단어 백준 3986번 c++ (두번째 풀기)  (0) 2022.02.11
Hasing 백준 15829번 c++  (0) 2022.02.11
시리얼 번호 백준 1431번 c++  (0) 2022.02.10
 
스택을 다룰때 자주 실수하는 것
st.top() 을 접근하기 전에, !st.empty()  스택이 비어있지 않은지 확인해야 한다.
 
#include <bits/stdc++.h>
using namespace std;

int n, answer;
string word;

bool check(string input){
  stack<char> st;

  int slen = input.length();
  if (slen % 2 == 1) return false;

  st.push(input[0]);
  for(int i = 1; i < slen; i++){
    if(!st.empty() && st.top() == input[i]) st.pop();
    else st.push(input[i]);
  }
  if(st.empty()) return true;
  else return false;
}

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

  cin >> n;
  while(n--){
    cin >> word;
    if (check(word)) answer++;
  }
  cout << answer;
  return 0;
}
 
짝이 맞으려면 문자열 길이가 일단 짝수여야 한다. 
 
문자열을 길이만큼 인덱스로 순회한다. 
스택의 제일 위의 top 글자가 현재 인덱스 글자와 같으면, top을 pop시킨다. 
현재 인덱스 글자 와 다르면, 현재 인덱스 글자를 push한다. 
 
순회가 끝났을 때 스택이 비어있어야 좋은 단어다. 
728x90
저작자표시 비영리 변경금지

'알고리즘 > 백준' 카테고리의 다른 글

쇠막대기 백준 10799번 c++  (0) 2022.02.13
괄호 백준 9012번 c++  (0) 2022.02.13
Hasing 백준 15829번 c++  (0) 2022.02.11
시리얼 번호 백준 1431번 c++  (0) 2022.02.10
곱셈 백준 1629번 c++  (0) 2022.02.09
 
 
모듈러 연산의 성질을 이용한 문제다. 
 (a * b ) mod n == (a mod n) * (b mod n)
 
#include <bits/stdc++.h>
using namespace std;

long long MOD = 1234567891;
long long MUL = 31;
int L;
string input;

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

  cin >> L >> input;

  long long answer = 0; // 합 누적
  long long R = 1; // 제곱근 처음에 1로 시작

  for(int i = 0; i < L; i++){
    // input[i] - 'a' + 1 : 문자의 인덱스. a는 1이 나오도록.
    long long idx = input[i] - 'a' + 1;
    answer = (answer + (idx * R)) % MOD;
    R = (R * MUL) % MOD; // 곱할 숫자
  }
  // 마지막에 항상 % MOD를 해서 숫자가 커지는 것을 방지한다
  cout << answer;

  return 0;
}
 

 

728x90
저작자표시 비영리 변경금지

'알고리즘 > 백준' 카테고리의 다른 글

괄호 백준 9012번 c++  (0) 2022.02.13
좋은 단어 백준 3986번 c++ (두번째 풀기)  (0) 2022.02.11
시리얼 번호 백준 1431번 c++  (0) 2022.02.10
곱셈 백준 1629번 c++  (0) 2022.02.09
큰 수 A+B 백준 10757번 c++  (0) 2022.02.09

+ Recent posts

티스토리툴바