글 읽기 - 96%에서 막힙니다

yuiyui128 5년 전 0

곱셈값과 나눗셈값을 미리 저장하여 공배수로 곱셈을 모두 나눠주었습니다.

나눠진 곱셈으로 모드연산을 하여 답을 찾아내는 방법으로 진행했는데, 96%애서 막히네요.

접근 방법을 점화식을 이용한 dp로 바꿔야 할까요??

#include <iostream>
#include <vector>

using namespace std;

int N, K;
vector<int> m,d;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N >> K;
    if( K > N/2) {
        K = N - K;
    }
    for(int i = 0 ; i < K; i++){
        m.push_back(N-(i)); // 곱셈 값
        d.push_back(i+1); // 나눗셈 값
    }
    for(int i = K-1; i >= 0; i--){ // 미리 약분한다
        for(int j = 0 ; j < m.size(); j++){
            for(int k = 2; k <= d[i]; k++){
                if( m[j] % k == 0 && d[i] % k == 0){ // 공배수를 찾아 나눈다
                    m[j] /= k;
                    d[i] /= k;
                    if(d[i] == 1) break;
                }
            }
        }
    }
    int ans = 1;
    for(int i:m){
        ans = ans * i % 10007; // 모드 연산하며 곱한다
    }
    cout << ans;
}

amatuer789 5년 전 1

for문 조건문 d[i]가 바뀌는 부분이 불안하네요.

예외 case 입니다.

% 배열은 연산 후, 상태 입니다.

입력 : 55 8

배열 m : 11 3 53 13 51 25 7 12

배열 d : 1 1 1 2 1 1 1 1

결과 : 9306

yuiyui128 5년 전 0

아 그렇네요! 아직 갈 길이 먼것을 많이 느낍니다 ㅠㅠ

덕분에 많이 배웠습니다! ㅎㅎ 감사합니다

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

문제

문제

출처

ICPC

96%에서 막힙니다

yuiyui128 5년 전 0

amatuer789 5년 전 1

yuiyui128 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말