문제링크

처음에는 if else 조건문으로 분기해서 풀었다.
다른 분들의 코드를 보니 xor 연산을 하길래 xor 연산을 적용해서 짧은 코드로 다시 풀었다. 
xor은 다르면 1을 출력하니까, 같은 수는 무시하고 다른 수만 남는다. 
(30, 20)
(10, 10)
(10, 20)
3 점을 보면 규칙을 발견할 수 있는데, 하나 남는 수들이 답으로 나와야 한다. 즉, (30, 10) 
따라서  30, 10, 10 중에서 같은 것들은 빼고, ‘다른 수'만 남겨야 하기 때문에 xor 연산을 이용할 수 있다. 
 
#include <bits/stdc++.h>
using namespace std;

int a, b;

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

  vector<pair<int,int>> v;
  for(int i = 0; i < 3; i++){
    cin >> a >> b;
    v.push_back({a, b});
  }

  if(v[0].first == v[1].first)
    cout << v[2].first << ' ';
  else if(v[1].first == v[2].first)
    cout << v[0].first << ' ';
  else
    cout << v[1].first << ' ';

  if(v[0].second == v[1].second)
    cout << v[2].second << ' ';
  else if(v[1].second == v[2].second)
    cout << v[0].second << ' ';
  else
    cout << v[1].second << ' ';

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

int a, b, aa, bb;

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  
  cin >> a >> b;
  for(int i = 0; i < 2; i++) {
    cin >> aa >> bb;
    a ^= aa;
    b ^= bb;
  }
  cout << a << ' ' << b;
  return 0;
}
 
728x90
저작자표시 비영리 변경금지 (새창열림)

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

하얀 칸 백준 1100번 c++  (0) 2022.02.21
다이얼 백준 5622번 c++  (0) 2022.02.21
백설 공주와 일곱 난쟁이 백준 3040번 c++  (0) 2022.02.20
색종이 만들기 백준 2630번 c++  (0) 2022.02.20
최소 힙 백준 1927번 c++  (0) 2022.02.19

문제링크 

 

9명 중에 2명을 뽑아야 한다. 

전체 9명의 숫자의 합을 totalsum이라고 구해둔다. 

totalsum - 2명의 숫자를 해야 한다. 2명을 고르려면 이중 반복문 또는 next_permutation 을 쓰면 된다. 

 

크기 9의 배열 2개가 필요하다. 

난쟁이숫자 배열 hat {7, 8, 10, 13, 15, 19, 20, 23, 25}

조합 배열     check  {0, 0, 0, 0, 0, 0, 0, 1, 1}  -> 난쟁이 2개 조합을 골라야하니까 1이 2개 

 

check 배열을 next_permutation() 하면, 1의 위치가 달라진다. 따라서 1의 위치에 해당하는 숫자를 선택하면 된다. 

 

주의 : next_permutation()을 쓸 때, 초기에 배열이 오름차순으로 정렬되어 있어야한다. 

 [불가능]  check  {1, 1, 0, 0, 0, 0, 0, 0, 0} <- 이것이 이미 next_permutation()의 마지막 결과물이기 때문이다. 

 

만약 배열 초기값이 {1, 2, 3} 이라면, next_permutation()의 마지막 결과는 {3, 2, 1}이 된다. 

 

"맞았습니다" 코드링크 

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

int totalsum;

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

  vector<int> hat(9);
  vector<int> check(9);
  check[7] = check[8] = 1;

  for(int i = 0; i < 10; i++){
    cin >> hat[i]; totalsum += hat[i];
  }

  do{
    int temp = 0;
    for(int i = 0; i < 9; i++){
      if(check[i])temp += hat[i];
    }
    if((totalsum - temp) == 100){
      for(int i = 0; i < 9; i++){
        if(!check[i]) cout << hat[i] << '\n';
      }
    }
  }while(next_permutation(check.begin(), check.end()));

  return 0;
}
728x90
저작자표시 비영리 변경금지 (새창열림)

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

다이얼 백준 5622번 c++  (0) 2022.02.21
네 번째 점 백준 3009번 c++  (0) 2022.02.21
색종이 만들기 백준 2630번 c++  (0) 2022.02.20
최소 힙 백준 1927번 c++  (0) 2022.02.19
ATM 백준 11399번 c++  (0) 2022.02.19
 
모든 칸을 확인했을 때, 결과는 2가지다. 
칸의 색깔 비교는 첫 칸을 기준으로 한다. 
(0,0) 부터 (3,3)까지 4x4 만큼의 사각형을 확인한다고 가정한다. 한 변의 길이는 4 다. 
 
1) 모든 칸을 확인했을 때 모두 같은색임  -> 첫 칸 색깔에  카운팅++ 하고 끝낸다. 
 
2) 모든 칸을 확인하는데 첫 칸과 다른 색 발견 -> 4의 반토막인 길이 2의 사각형 4개를 탐색한다. 
4개로 쪼개지니까 재귀함수를 4번 돌려야한다. 
 
(0, 0) 부터 2길이만큼 탐색한다. 
(0, 1)부터 2길이만큼 탐색한다. 
(1, 0)부터 2길이만큼 탐색한다. 
(1,1)부터 2길이만큼 탐색한다. 
 
#include <bits/stdc++.h>
using namespace std;

int N, white_cnt, blue_cnt; // 하양 0, 파랑 1 로 표시
int arr[129][129];

void check(int x, int y, int len){ // 행, 열, 한 변 길이

  int color = arr[x][y];
  for(int i = x; i < x+len; i++){ // 행
    for(int j = y; j < y+len; j++){ // 열
      if(color != arr[i][j]){
        check(x, y, len/2);
        check(x, y + len/2, len/2);
        check(x + len/2, y, len/2);
        check(x + len/2, y + len/2, len/2);
        return;
      }
    }
  }
  if(color == 1) blue_cnt++; // 전부 1이었다면 파랑 카운팅 
  else white_cnt++;
}

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

  cin >> N;

  for(int i = 0; i < N; i++) // 입력 받기
    for(int j = 0; j < N; j++)
      cin >> arr[i][j];

  check(0, 0, N);
  cout << white_cnt << '\n' << blue_cnt; 
  return 0;
}
 
 
728x90
저작자표시 비영리 변경금지 (새창열림)

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

네 번째 점 백준 3009번 c++  (0) 2022.02.21
백설 공주와 일곱 난쟁이 백준 3040번 c++  (0) 2022.02.20
최소 힙 백준 1927번 c++  (0) 2022.02.19
ATM 백준 11399번 c++  (0) 2022.02.19
나는야 포켓몬 마스터 이다솜 백준 1620번 c++  (0) 2022.02.19
 
priority queue을 오름차순으로 만드려면 greater클래스를 넣어준다. 
 greater<int> : 오름차순
 less<int> : 내림차순 
priority_queue<int, vector<int>, greater<int>> pq;
 
#include <bits/stdc++.h>
using namespace std;

int n, input;
priority_queue<int, vector<int>, greater<int>> pq;

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

  cin >> n;
  while(n--){
    cin >> input;
    if(pq.empty() && input == 0){
      cout << 0 << '\n';
    }else if(input == 0){
      cout << pq.top() << '\n';
      pq.pop();
    }else{
      pq.push(input);
    }
  }
  return 0;
}
 
728x90
저작자표시 비영리 변경금지 (새창열림)

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

백설 공주와 일곱 난쟁이 백준 3040번 c++  (0) 2022.02.20
색종이 만들기 백준 2630번 c++  (0) 2022.02.20
ATM 백준 11399번 c++  (0) 2022.02.19
나는야 포켓몬 마스터 이다솜 백준 1620번 c++  (0) 2022.02.19
최대 힙 백준 11279번 c++  (0) 2022.02.19
 
사람들이 소요하는 시간이 오름차순이 되어야 누적합이 최소가 된다. 
map <고객번호, 소요시간> 으로 받고, 
소요시간 기준(map의 value) 으로 오름차순이 되도록 정렬한다. 
 
map<int,int>  → vector<pair<int,int>> 변환 
  vector<pair<int,int>> v(bmap.begin(), bmap.end()); // map -> vector
 
sort() 함수에 비교함수 작성 
bool comp(pair<int,int> &left, pair<int,int> &right){
  if(left.second < right.second) return true;
  else return false; 
}
sort(v.begin(), v.end(), comp);  // value 기준으로 오름차순 정렬
 
vector를 순회하며 각각에 대한 누적 합을 acc_vec 벡터에 저장했다. 
 

 

acc_vec 벡터의 누적합은 accumulate() 함수로 구한다. 
  answer = accumulate(acc_vec.begin(), acc_vec.end(), 0); // 마지막 인자는 합의 초기값
 
 
#include <bits/stdc++.h>
using namespace std;

int n, input;
long long accum, answer;
map<int, int> bmap;
vector<int> acc_vec; // 누적합을 저장

bool comp(pair<int,int> &left, pair<int,int> &right){
  if(left.second < right.second) return true;
  else return false; 
}

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

  cin >> n;

  for(int i = 1; i <= n; i++){
    cin >> input;
    bmap.insert({i, input});
  }

  vector<pair<int,int>> v(bmap.begin(), bmap.end()); // map -> vector
  sort(v.begin(), v.end(), comp);  // value 기준으로 오름차순 정렬

  for(auto i : v){
    accum += i.second;
    acc_vec.push_back(accum);
  }
  answer = accumulate(acc_vec.begin(), acc_vec.end(), 0); // 마지막 인자는 합의 초기값
  cout << answer;
  return 0;
}
 
 
728x90
저작자표시 비영리 변경금지 (새창열림)

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

색종이 만들기 백준 2630번 c++  (0) 2022.02.20
최소 힙 백준 1927번 c++  (0) 2022.02.19
나는야 포켓몬 마스터 이다솜 백준 1620번 c++  (0) 2022.02.19
최대 힙 백준 11279번 c++  (0) 2022.02.19
집합 백준 11723번 c++  (0) 2022.02.19
 
처음에는 map<이름, 번호> 맵 하나로 풀었다가 시간초과가 났다. 
입력 개수가 최대 10만이기 때문에 하나의 map으로는 시간초과가 난다. 
그래서 map을 2개 만들어놔서 풀었다.  
 
하나는 이름을 입력하면 번호를 값으로 갖는 smap<이름, 번호> 이다. 
다른건 숫자를 입력하면 이름을 값으로 갖는 nmap<번호, 이름> 이다. 
이렇게 하면 반복문을 안돌아도 값을 바로 찾을 수 있다. 
 
#include <bits/stdc++.h>
using namespace std;

int n, m; // 포켓몬개수, 문제개수
string name, input;
map<string, int> smap; // 문자 입력 -> 숫자출력
map<int, string> nmap; // 숫자 입력 -> 문자출력

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

  cin >> n >> m;
  for(int i = 1; i <= n; i++){
    cin >> name;
    smap.insert({name, i}); // {이름, 인덱스}
    nmap.insert({i, name}); // {인덱스, 이름}
  }

  for(int i = 0; i< m; i++){
    cin >> input;
    if(isdigit(input[0])){ // 숫자라면 0이 아닌 수가 나온다
      cout << nmap[atoi(input.c_str())]<< '\n';
    }else{ // 문자
      cout << smap[input] << '\n';
    }
  }

  return 0;
}
 
728x90
저작자표시 비영리 변경금지 (새창열림)

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

최소 힙 백준 1927번 c++  (0) 2022.02.19
ATM 백준 11399번 c++  (0) 2022.02.19
최대 힙 백준 11279번 c++  (0) 2022.02.19
집합 백준 11723번 c++  (0) 2022.02.19
바이러스 백준 2602번 c++  (0) 2022.02.19
 
항상 최대값이 뭔지 알고 있어야 하니까, priority_queue를 이용했다. 
우선순위 큐의 top()은 항상 최대 값을 알고 있다. 
pop() 하면 항상 최대값이 제거된다. 
 
#include <bits/stdc++.h>
using namespace std;

int n;
long long input;
priority_queue<long long> pq;

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

  cin >> n;

  while(n--){
    cin >> input;
    if(pq.empty() && input == 0){
      cout << 0 << '\n';
    }else if(input == 0){ // 출력 및 제거
      cout << pq.top() << '\n';
      pq.pop();
    }else{
      pq.push(input);
    }
  }

  return 0;
}
 
728x90
저작자표시 비영리 변경금지 (새창열림)

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

ATM 백준 11399번 c++  (0) 2022.02.19
나는야 포켓몬 마스터 이다솜 백준 1620번 c++  (0) 2022.02.19
집합 백준 11723번 c++  (0) 2022.02.19
바이러스 백준 2602번 c++  (0) 2022.02.19
비밀번호 찾기 백준 17219번 c++  (0) 2022.02.17

+ Recent posts

티스토리툴바