글 읽기 - 진짜 줄이고 줄였는데 시간초과가 뜨네요...ㅜㅜ

oreochoco 7년 전 1

비트마스크 3진법으로 짜봤는데 계속 시간초과가 뜨네요...

더 나은 알고리즘이 있는건지 아니면 더 코드를 짧게 줄일수 있는건지 도와주세요...

#include <stdio.h>
using namespace std;
 
int N;
int place[300005][11];
int po[9];

void precalc(){
    po[0]=1;
    for(int i=1;i<=8;i++) po[i]=10*po[i-1];
}
 
int main(){
    precalc();
    scanf("%d",&N);
    for(int i=1;i<=N;i++) for(int j=1;j<=9;j++) scanf("%d",&place[i][j]);
    int tmp,flag,p,num,mini=300005,maxi=0;
    for(int i=0;i<=19682;i++){
        num=0;
        for(int j=1;j<=N;j++){
            tmp=i,flag=1;
            for(int k=1;k<=9;k++){
                p=tmp%3;tmp/=3;p++;
                if(place[j][k]==p){flag=0;break;}
            }
            if(flag) num++;
        }
        if(num<mini) mini=num;
        if(num>maxi) maxi=num;
    }
    printf("%d %d",mini,maxi);
}

yukariko 7년 전 0

매 반복마다 N번 돌지않는 방법을 떠올려보세요.

힌트는 3진법입니다.

oreochoco 7년 전 0

오 해결했습니다 ㅋㅋㅋㅋ각 학생에대해서 안걸리는것을 떠올려야됐군요...감사합니다!

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

문제

문제

출처

ICPC

진짜 줄이고 줄였는데 시간초과가 뜨네요...ㅜㅜ

oreochoco 7년 전 1

yukariko 7년 전 0

oreochoco 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말