글 읽기 - 동전2 시간초과 원인

heehcs 6년 전 0

안녕하세요,
동전2가 일차원 배열을 사용하여 어떤식으로 업데이트되는지 원리는 이해했는데,
아래코드 제출시 시간 초과가 나네요. 원인이 뭘까요?

#include <cstdio>
#include <cstring>
int a[101]; // d[1..n]: 동전타입이 들어갈 배열
int d[10001]; // d[1..k]: 합계를 만드는데에 들어가는 동전의 최소개수

int main() {
  int n, k;
  scanf("%d %d", &n, &k);
  for(int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  
  memset(d, -1, sizeof(d));
  d[0] = 0;
  for(int i = 1; i <= n; i++) {
    for(int j = 0; j <= k; j++) {
      if(j-a[i] < 0) continue;
      if(d[j-a[i]] == -1) continue; 
      if(d[j] == -1 || d[j] > d[j-a[i]] + 1) 
	    d[j] = d[j-a[i]] + 1; 	
    }
  }
  printf("%d\n", d[k]);
}

heehcs 6년 전 1

for문 내부의 if구문 3개가 문제였네요. else if로 바꾸고 AC 받았습니다.

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

문제

문제

출처

ICPC

동전2 시간초과 원인

heehcs 6년 전 0

heehcs 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말