JArchive 프로그래밍 일기

문제링크:  백준 9471 피사노 주기 

“ 피보나치 수열을 m으로 나눈 나머지가 P길이의 주기를 가진다.  “

그래서 벡터 v는 필요 없고 숫자 m1, m2만 필요하다. 

#include <bits/stdc++.h>
#define endp '\n';
using namespace std;

int p, n, m;

int pisano(int mod){

  int cnt = 0; // cnt 번째 피보나치 수
  int m1 = 0, m2 = 1; // 0과 1이 순서대로 나오면, 주기 발견.
  int tempsum = 0;

  while(1){
    tempsum = m1 + m2;
    m1 = m2;
    m2 = tempsum % mod;
    cnt++;
    if(m1 == 0 && m2 == 1) break;
  }

  return cnt;
}

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

  cin >> p;

  for(int i = 1; i <= p; i++){
    cin >> n >> m;
    cout << n << ' ' << pisano(m) << endp;
  }

  return 0;
}

문제

1로 만들기2 백준 12852

"맞았습니다"코드

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

int D[1000002];
int n;

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

  cin >> n;

  D[1] = 0;
  D[2] = D[3] = 1;

  for(int i = 4; i <= n; i++) D[i] = 1e9;

  for(int i = 4; i <= n; i++){
    if(i % 3 == 0) D[i] = min(D[i/3] + 1, D[i]);
    if(i % 2 == 0) D[i] = min(D[i/2] + 1, D[i]);
    D[i] = min(D[i-1] + 1, D[i]);
  }

  cout << D[n] << '\n';

  while(1){
    cout << n << ' ';
    if(n == 1) break;
    if(n % 3 == 0 && (D[n/3] + 1) == D[n]) n /= 3;
    else if(n % 2 == 0 && (D[n/2] + 1) == D[n]) n /= 2;
    else n--;
  }
  return 0;
}

리뷰

bfs로 풀어야하나? 싶었다.
9를 3으로 나누는 연산을 하면, D[9] = D[3] + 1 임을 적어보니까.
1을 만드는 '가장 적은 횟수'를 메모이제이션 하는 dp 같았다.

주어진 숫자에서 1을 만드는게 아니라, 1에서 주어진 숫자로 갈 때 최소 연산 횟수를 찾는 반복문을 만들었다.

최소 연산 횟수를 찾는거니까, 메모이제이션 배열 D는 큰 수로 초기화 해뒀다.

문제

피보나치 수2 백준 2748

"맞았습니다" 코드

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

long long F[91];
int n;

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

  cin >> n;

  F[1] = 1;
  for(int i = 2; i <= 90; i++) F[i] = F[i-1] + F[i-2];
  cout << F[n];

  return 0;
}

리뷰

메모이제이션을 이용해 반복 계산을 피했다.
숫자가 커지니까 long long 을 써야한다.

문제

카드 백준 11652

"맞았습니다" 코드

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

int maxcnt = 0;
long long cnt, n, answer = 0;
map<long long, int> nmap;

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

  cin >> cnt;

  while(cnt--){
    cin >> n;
    nmap[n]++;
  }

  for(auto m: nmap){
    if(m.second > maxcnt){
      maxcnt = m.second;
      answer = m.first;
    }
  }

  cout << answer;

  return 0;
}

리뷰

map 은 key값이 중복되지 않으면서, 자동으로 오름차순 정렬된다.
value 에 숫자의 개수를 저장했다.

key 값들이 모두 같은 개수라면, 작은 수를 답으로 내야 하니까.
key를 정렬해주는 map 이 적절했다.

먼저, 입력된 숫자 마다의 개수를 센다.
그 다음 map을 반복문으로 순회하는데, 발견한 최대 개수와 최대 개수의 숫자를 저장하는 조건문을 둔다.
value는 maxcnt에 저장하고, key는 answer에 저장하는 것이다.

최대 개수보다 초과해야 maxcnt, answer를 갱신하니까,
key 값들이 모두 같은 개수라도, '작은 수'key 를 답으로 낼 수 있다.

문제

구간 합 구하기4 백준 11659

"맞았습니다" 코드

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

int n, m; // 수의 개수 n, 합을 구해야 하는 횟수 m
int A[100005];
long long D[100005];
int i, j;

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

  cin >> n >> m;

  cin >> A[1];
  D[1] = A[1];
  for(int i = 2; i<= n; i++){
    cin >> A[i];
    D[i] = D[i-1] + A[i];
  }

  while(m--){
    cin >> i >> j;
    cout << D[j]-D[i-1] << '\n';
  }

  return 0;
}

리뷰

입력받을 때 마다 누적 합을 저장하는 배열 D를 만든다.
만약 3 에서 5의 구간합을 계산하려면 ,
15 의 합을 저장한 D[5] 에서 12의 합을 저장한 D[2]를 빼면 된다.

문제

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() 모두의 코드 레퍼런스