JArchive 프로그래밍 일기

문제링크 

DP 메모이제이션으로 풀 수 있었다. 

n번째 피보나치 수를  출력하면 된다. 

수의 크기 n이 크지않아서 long long 배열로 충분했다. 

"맞았습니다." 코드 

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

long long D[47];
int n;

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

  cin >> n;

  D[1] = D[2] = 1;
  for(int i = 3; i <= 45; i++){
    D[i] = D[i-1] + D[i-2];
  }

  cout << D[n];
  return 0;
}

백준 2749번 피보나치 수 3

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

long long n, cnt;
vector<int> v;

void pisano(int m){
  v.push_back(0); // 0번째 피보나치 수
  v.push_back(1); // 1번째 피보나치 수
  v.push_back(1); // 2번째 피보나치 수

  cnt = 2; // 3번째 피보나치 수를 구하기 위해 2번째와 1을 연산해야 한다.

  while(1){
    v.push_back((v[cnt] + v[cnt-1]) % m);
    cnt++;
    if(v[cnt] == 0 && v[cnt-1] == 1) break; // 주기를 구한 순간.
  }

}

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

  cin >> n;

  pisano(1000000);
  cout << v[n % cnt];

  return 0;
}

문제링크:  백준 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]를 빼면 된다.