글 읽기 - 1700번 질문이요..

dong6788 9년 전 0

멀티탭이 다 꽂혀있을 때 eviction algorithm으로는 탭에 꽂혀있는 애들 중 가장 나중에 다시 나오는 것(혹은 안 나오는 것. 여러개일경우 그 중 숫자가 낮은것)을 빼는 알고리즘으로 구현하였습니다.

예제를 포함해서 왠만한 Test cases들은 다 되는 것 같은데 틀렸다고 뜨네요 ㅠ 한번 봐 주시면 감사하겠습니다

#include <stdio.h>

int tab[110];
int tab2[110];
int elec[110];

int main(){
	int n,k,i,i2,j,m,x,cnt,sw,su;
	sw = 0;
	cnt = 0;
	scanf("%d %d", &n, &k);
	for(i=0;i<k;i++) scanf("%d", &elec[i]);
	for(i=0;i<k;i++){
		for(j=0;j<n;j++) tab2[j] = 1;
		x = elec[i];
		sw = 0;
		for(j=0;j<n;j++){
			if(tab[j] == x){
				sw = 1;
				break;
			}
			else if(tab[j] == 0){
				tab[j] = x;
				sw = 1;
				break;
			}
		}
		if(sw == 1) continue;
		cnt++;
		for(m=i+1;m<k;m++){
			for(i2=0;i2<n;i2++){
				if(tab[i2] == elec[m]){
					tab2[i2] = 0;
					break;
				}
			}
			su = 0;
			for(i2=0;i2<n;i2++) su += tab2[i2];
			if(su <= 1) break;
		}

        for(m=0;m<n;m++){
            if(tab2[m] == 1) break;
        }
		tab[m] = x;
	}
	printf("%d\n", cnt);
}

pichulia 9년 전 1

알고리즘 자체는 맞는거 같습니다. 단 문제가 되는 때가 있는데요

그건 바로 n = 1 일 때 입니다.

실제로 데이터

1 3

1 2 1

을 넣으면

2가 나와야하는데 답으로 1이 나오는 것을 확인할 수 있습니다.

pichulia 9년 전 1

초고속으로 고치는 법

        for(m=i+1;m<k;m++){
            su = 0;
            for(i2=0;i2<n;i2++) su += tab2[i2];
            if(su <= 1) break;
            for(i2=0;i2<n;i2++){
                if(tab[i2] == elec[m]){
                    tab2[i2] = 0;
                    break;
                }
            }
        }

dong6788 9년 전 0

구멍이 하나이고 새로운 게 들어왔을때는 무조건 빼줘야 하는데 쓸데없는 연산을 하느라 오류가 나는거였네요ㅋㅋ 지적 감사합니다!

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

문제

문제

출처

ICPC

1700번 질문이요..

dong6788 9년 전 0

pichulia 9년 전 1

pichulia 9년 전 1

dong6788 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말