글 읽기 - 왜 틀리는걸까요....

aigorithm 3년 전 0

K값을 소인수분해한 결과를 vector에 저장하고, 그를 통해서 N!에서 찾아 계산하는 방법으로 구현했습니다.

그런데 계속 틀렸습니다가 뜹니다..

어디를 놓치고 있는걸까요? ㅠㅠ 반례를 못찾겠습니다.

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

vector<pair<int, int> > seq; // 소인수, 지수 형태로 저장됨

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

  int N, K;
  while(true){
    cin >> N >> K;
    if(cin.eof()) break;

    seq.clear(); // seq vector 초기화
    // K의 소인수 분해한 결과를 벡터에 삽입
    for (int i = 2; i*i <= K; i++) {
      int factor = i;
      if(K%i == 0)
        seq.push_back({factor, 0});
      while(K % i == 0){
        seq[seq.size()-1].second++;
        K/= i;
      }
      if(K < i) break;
    }
    // for문이 끝난 후 남은 K의 범위가 아래와 같다면 seq에 추가
    if(K > 1 && K < N)
      seq.push_back({K,1});
    // ====== 여기까지 했을 때 seq에 K의 소인수 분해한 결과가 저장됨

    // 저장된 seq를 가지고 N! 에서 각 소인수가 몇번 등장했는지 찾음
    int res = 1;
    for (int i = 0; i < seq.size(); i++) {
      int sum_val = 0;  // 지수를 찾기위한 변수
      int factor = seq[i].first;  // 소인수
      for (int j = factor; j < N; j*= factor) {
        int temp = N/j; // 각 j의 숫자가 1~N까지 몇개 있는지 찾고
        if((sum_val + temp) >= seq[i].second){ // 만약에 K의 지수보다 크거나 같다면 K의 지수로 바꾸고 for문 종료.
          sum_val = seq[i].second;
          break;
        }
        else sum_val += temp; // 그게 아니면 일단 계속 카운팅 한다.
      }
      res *= pow(factor, sum_val); // 최종 결과값을 위해 for문 돌면서 지수 제곱꼴을 계속 곱해줌
    }
    cout << res << "\n";
  }

  return 0;
}

dldyddlwl 3년 전 1

이 경우를 생각해봅시다.

2 2를 넣어보시면, 실제로는 2! 과 2니까, 2와2 입니다. 따라서, 최대공약수는 2가 나와야 합니다. 그런데 글쓴이님의 코드는 1이 나옵니다.

for (int i = 2; i*i <= K; i++) 이 조건을 보시면, K가 2일 때는 i*i <= K, (i는 2부터 시작하므로 ) 첫 조건 4 <= K = 2 가 되므로, for loop에 들어가지도 못합니다.

그리고 여기 if(K > 1 && K < N) 이 부분을 보시면, N이 2로 주어진다면 K값과 관계없이, if문 안으로 들어갈 수 없습니다. 따라서, 2 2의 경우에는 제대로 처리될 수가 없습니다.

aigorithm 3년 전 0

아!! 제가 그 부분 코드를 잘못짰었네요 ㅠㅠ 정말 정말 감사합니다. for loop부분은 전혀 생각하지 못하고 있었네요. 좋은 답변 감사드립니다!!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

왜 틀리는걸까요....

aigorithm 3년 전 0

dldyddlwl 3년 전 1

aigorithm 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말