JArchive 프로그래밍 일기

문제

1,2,3 더하기 9095

"맞았습니다"코드

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

int tc, n; // n은 11보다 작은 양수다.
int D[12];
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> tc;
  D[1] = 1, D[2] = 2, D[3] = 4;
  for(int i = 4; i <= 11; i++){
    D[i] = D[i-1] + D[i-2] + D[i-3];
  }
  while(tc--){
    cin >> n;   cout << D[n] << '\n';
  }
  return 0;
}

리뷰

점화식 찾는것이 쉽지 않았던 문제다.
D[i] == i를 1,2,3의 합으로 나타내는 방법 개수 라고 정했다.

일단 작은 수를 써보면서 점화식을 도출해봤다.
D[1] = 1개 (1)
D[2] = 2개. (1+1, 2)
D[3] = 4개. (1+2, 2+1, 1+1+1, 3)
D[4] = 7개. (1+1+1+1, 3+1, 2+1+1, 1+2+1, 1+1+2, 1+3, 2+2)

D[3]과 D[4]만 비교해보면.
D[3] = 4개. (1+2, 2+1, 1+1+1, 3)
D[4] = 7개. (1+1+1+1, 3+1, 2+1+1, 1+2+1, 1+1+2, 1+3, 2+2)

D[3]은 3을 만드는 4개 방법이 있다.
(1+2, 2+1, 1+1+1, 3) 이 4개의 방법에 +1만 붙이면 4가 만들어진다.
(1+2 +1, 2+1 +1, 1+1+1 +1, 3 +1)

D[2]은 2을 만드는 2개 방법이 있다.
(1+1, 2) 이 2개 방법에 +2만 하면 4가 만들어진다.
(1+1 +2, 2 +2)

D[1]은 (1) 1개 방법이 있는데. 여기에 +3만하면 4가 만들어진다.

이처럼 D[1], D[2], D[3] 의 방법 개수를 더하면 D[4]가 된다.
D[i] = D[i-1] + D[i-2] + D[i-3]

문제

시리얼 번호 백준 1431

"맞았습니다."코드

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

string numberst = "0123456789";
vector<string> v;

bool cmp(string &a, string &b){
  int asize = a.size(), bsize = b.size();
  int asum = 0, bsum = 0;

  if(asize != bsize) return asize < bsize;
  for(int i = 0; i < asize; i++){
    if(numberst.find(a[i]) <= numberst.size()) asum += (a[i] - '0');
  }
  for(int i = 0; i < bsize; i++){
    if(numberst.find(b[i]) <= numberst.size()) bsum += (b[i] - '0');
  }
  if(asum != bsum) return asum < bsum;
  return a < b;
}
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int n;
  string st;
  cin >> n;
  for(int i = 0; i < n; i++){ cin >> st; v.push_back(st);}
  sort(v.begin(), v.end(), cmp);
  for(auto i : v) cout << i << '\n';
  return 0;
}

리뷰

비교함수를 조건대로 구현하는건 어렵지 않게 느껴졌는데.
find 함수를 틀리게 쓰는 것을 모르고.. 시간을 조금 허비했다.

numberst.find(b[i]) <= numberst.size()

이렇게 써야 하는데

[ 틀린 코드 ] numberst.find(b[i]) <= b.size() 

이렇게 b문자열 사이즈와 비교하고 있어서 틀린거였다.

숫자 문자열 numberst 를 만들어 놨다.
문자열을 순회하면서 이 문자가 numberst의 어디 인덱스에 속하냐를 묻는건데.

..... 앞으로 조심하자.

string 의 find() 함수 c++ reference
첫 번째로 매칭되는 문자의 인덱스를 리턴해준다.

find() 함수
범위 안에 원하는 값을 찾는 함수.

int myints[] = {10, 20, 30, 40};
int* p;

p = std::find(myints, myints + 4, 30);
if (p != myints + 4)
    std::cout << "Element found in myints: " << *p << '\n';
else
    std::cout << "Element not found in myints\n";

find() 모두의 코드 레퍼런스

문제

국영수 백준 10825

"맞았습니다."코드

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

struct student{
  string name;
  int kor, eng, math;
};

int n, kor, eng, math;
string st;
vector<student> v;

bool cmp(student &a, student &b){
  if(a.kor == b.kor && a.eng == b.eng && a.math == b.math) return a.name < b.name;
  else if(a.kor == b.kor && a.eng == b.eng) return a.math > b.math; // 수학 감소하는 순서
  else if(a.kor == b.kor) return a.eng < b.eng; // 영어 증가하는 순서
  else return a.kor > b.kor; //국어 감소하는 순서
}
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n;
  for(int i = 0; i < n; i++){
    cin >> st >> kor >> eng >> math;
    student s = {st, kor, eng, math};
    v.push_back(s);
  }
  sort(v.begin(), v.end(), cmp);
  for(auto i : v) cout << i.name << '\n';
  return 0;
}

리뷰

비교 함수를 정확히 구현해야 맞을 수 있는 문제였다.
비교 함수를 작성할 때 조건이 구체적인 것 부터 걸러내야 한다.
그래서 '모든 점수가 같으면' 이름이 사전순 증가 하게 출력하라는 조건부터 if문을 시작해야 한다.
문제에서 나오는 조건 대로 작성했다가 처음 풀었을 때 틀렸다.

문제

접미사 배열 11656

"맞았습니다"코드

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

string st;
vector<string> v;

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

  cin >> st;
  int stringlen = st.length();
  for(int i = 0; i < stringlen; i++) {
    string temp = st.substr(i);
    v.push_back(temp);
  }
  sort(v.begin(), v.end());
  for(auto i : v) cout << i << '\n';
  return 0;
}

리뷰

substr() 함수로 문자열의 특정 인덱스부터 끝까지 잘라냈다.

substr(2) = 2부터 끝까지 잘라내기
substr(2,5) = 2부터 5개 잘라내기

c++ 문자열 추출 substr 함수

문제

1로 만들기 1463

"맞았습니다"코드

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

int arr[1000005];
int x;

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

  cin >> x;
  arr[2] = 1; arr[3] = 1;
  for(int i = 4; i <= x; i++){
    arr[i] = arr[i-1]+1;
    if(i%3 == 0) arr[i] = min(arr[i], arr[i/3] + 1);
    if(i%2 == 0) arr[i] = min(arr[i], arr[i/2] + 1);
  }
  cout << arr[x];
}

리뷰

관찰이 필요한 DP문제다.

arr[i] = i를 1로 만들기 위해 필요한 연산 횟수의 최솟값

D[12]를 구할 때 어떤 과정인지, D[10]을 구할때 어떤 과정인지 구해보면 아이디어를 얻을 수 있었다.
3가지 연산 중에 최소 값을 찾아서 갱신해주면 된다.

1을 1로 만드는데 연산은 0번 필요하다. D[1] = 0
2를 1로 만드는데 연산은 1번 필요하다.(2로 나누거나 1을 빼기) D[2] = 1
이 문제에서는 D[1] 초기값만 정해주면 된다.

참고) 이 문제는 BFS로도 해결할 수 있다. dist 배열을 두고 초기값을 1로 한 뒤, x2, x3, +1로 뻗어나가면 답이 나온다.

문제

먹을 것인가 먹힐 것인가 백준 7795

"맞았습니다."코드

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

int tc, n, m, num;
vector<int> a, b;
int solve(){

  int answer = 0;
  sort(a.begin(), a.end());
  sort(b.begin(), b.end());

  for(int i = a.size()-1; i >= 0; i--){
    for(int j = b.size()-1; j >= 0; j--){
      if(a[i] > b[j]) {
        answer += j + 1;
        break;
      }
    }
  }
  return answer;
}

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

  cin >> tc;
  while(tc--){
    cin >> n >> m;
    a.clear(); b.clear();
    while(n--) { cin >> num; a.push_back(num); }
    while(m--){ cin >> num; b.push_back(num); }
    cout << solve() << '\n';
  }
  return 0;
}

리뷰

main 함수에서는 입력만 받았고. 핵심은 solve() 함수이다.
벡터 a와 b를 각각 정렬한다.

a의 가장 큰 수와 b의 가장 큰 수를 비교한다.
a[i] > b[j] 라면, b의 모든 수를 a[i]가 먹을 수 있다. 따라서 바로 answer를 증가시키고 break;한다.

그 다음 두 번째로 큰 숫자 a[i]와 b의 가장 큰 수를 비교한다.
a[i] > b[j] 를 만족하지 못하면, b의 인덱스 j를 감소시키면서 먹을 수 있을 때 까지 순회한다.
먹을 수 있는 크기가 나타나면 j+1만큼 크기를 answer에 더해준다.

문제

빈도 정렬 백준 2910

"맞았습니다" 코드

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;

int n, c, num;
map<int,int> idxm; // {숫자, 처음 나온 인덱스} 저장
map<int,int> recentm; // {숫자, 빈도} 저장
vector<pair<int,int>> v;

bool cmp(pair<int,int> a, pair<int,int> b){ // 빈도 내림차순, 인덱스 오름차순
  if(a.X == b.X) return idxm[a.Y] < idxm[b.Y];
  return a.X > b.X;
}
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> c;
  for(int i = 0; i < n; i++){
    cin >> num;
    recentm[num]++; // num의 빈도를 1 증가시킨다
    if(idxm[num] == 0 ){ // num이 처음 나왔다면, 인덱스를 저장한다.
      idxm[num] = i+1;
    }
  }

  // recentm {숫자, 빈도} -> {빈도, 숫자} 로 바꿔서 벡터에 저장
  for(auto & it : recentm){
    v.emplace_back(it.Y, it.X);
  }

  // 빈도를 기준으로 정렬하되, 인덱스 조건 고려하여 정렬하도록 cmp 함수 적용
  sort(v.begin(), v.end(), cmp);

  for(int i = 0; i < v.size(); i++){ // 숫자의 빈도(== v[i].X)만큼 숫자를 출력.
    for(int j = 0; j < v[i].X; j++){
      cout << v[i].Y << ' ';
    }
  }
  return 0;
}

리뷰

처음에는 벡터만을 생각해서 풀어서 감이 안오고 어렵게 느껴졌다.
key의 중복을 허용하지 않는 map을 이용해서 풀었다.

처음에 입력 받을 때 2개의 맵을 초기화한다.
(숫자, 빈도)를 저장하는 recentm map에 빈도를 저장한다.
(숫자, 숫자가 처음 나온 인덱스)를 저장하는 idxm map에 '숫자가 처음 등장한 인덱스'를 저장한다.

인덱스가 0이면 '처음 나왔다' 고 보기 때문에. 1+i를 인덱스로 저장했다.

빈도가 가장 많은 숫자가 앞에 와야 하니까 정렬이 필요하다.
map recentm {숫자, 빈도} 을 vector v {빈도, 숫자}로 바꿔서 저장한다.

여기서 vector.emplace_back()을 썼는데. vector.push_back()과 동일한 기능이다.

push_back() 과 달리 emplace_back()는 데이터를 삽입할 때 임시 객체를 생성하지 않아서 약간 더 빠르다고 한다.

빈도가 같은 경우에, '숫자가 처음 등장한 인덱스'가 작은것을 우선하라는 조건을 주기 위해 cmp 비교 함수를 넣고 sort() 한다.

정렬이 끝나면, 숫자를 '숫자의 빈도'만큼 출력해주면 되니까 이중 반복문으로 vector 를 순회하여 출력한다.

iterator로 순회하는 반복문 코드 2가지 형태를 배웠다.

  map<int,int> recentm; // {숫자, 빈도} 저장

  // 아래 2개 반복문은 똑같이 동작한다. 
  for(auto & it : recentm)

  for(auto it = recentm.begin(); it != recentm.end(); it++) 
}