글 읽기 - 7481 ATM놀이 틀렸다고 나오는데 무엇이 잘못된 걸까요?

nersery 7년 전 0

흠, 나머지를 이용해서 풀려고 했는데 아래 코드에서 어떤것이 잘못된 걸까요?

#include <cstdio>

int N,a,b,S,na,nb,temp,max_nb;

int main()
{
  scanf("%d",&N);
  for(int i=0; i < N; i++)
  {
    bool reversed, checker;
    scanf("%d %d %d",&a,&b,&S);
    if(b < a){
      temp = b;
      b = a;
      a = temp;
      reversed = true;
    }
    if(a > S && b > S)
      printf("%s","Impossible\n");
    else {
      max_nb = S / b;
      for(int k=0; k <= a; k++)
      {
        if((S%b + b*k)%a == 0){
          nb = max_nb - k;
          na = (S - b*nb) / a;
          reversed ? printf("%d %d\n",nb,na) : printf("%d %d\n",na,nb);
          checker = true;
          break;
        }
      }
      if(checker == false)
        printf("%s","Impossible\n");
    }
  }
  return 0;
}

도저히 모르겠어서 질문 드립니다 ㅠㅠ

nivea50 7년 전 1

a와 b값을 서로 바꾼 케이스는 reserved = true로 기록하신 것 같은데

다음 케이스에서는 안바꿀 수도 있으므로 케이스가 시작할때 마다 reserved = false로 초기화 시켜야 합니다.

2
3 2 8
2 1
2 3 8
2 1

nersery 7년 전 0

바꿨는데도 안되네요.. ㅠㅠ

nivea50 7년 전 1

^{22번째 줄 for문 조건식 for(int k=0; k <= max_nb; k++)}

그리고 checker 변수도 케이스마다 false로 초기화

이 2개 수정해보시겠어요?

nersery 7년 전 0

초기화는 완전히 제가 실수했네요! 지적감사합니다 ㅠㅠ

그냥 bool 변수, 변수 이렇게 하면 안되는가보네요.

근데 문제는 `for(int k=0; k<= max_nb; k++)`이 부분인데,

사실 k는 a까지만 봐도 되지 않나요? 어차피 a+1부터는 a로나눈 나머지가 동일할텐데요.

답을 고치면 무조건 나오는건 이해가 되는데 왜 시간초과가 안났는지 잘 모르겠네요.. 답변 늦어서 죄송합니다

nivea50 7년 전 1

알고리즘을 보면

입력받은 두 지폐 a ,b 중 금액이 작은 지폐를 a로, 큰 지폐를 b로 바꾼 상태에서

max_nb = S / b; 여기서 max_nb는 큰 지폐 b로 지불할 수 있는 최대 개수.

nb(지폐 b의 개수)는 0 ~ max_nb의 범위를 갖겠네요. 개수를 구하는 것이니 최소가 0이겠죠...

그러니 for문은 nb값이 max_nb로 시작해서 0이 될때까지 돌아야 합니다. 변수 k가 그 역할을 하구요..

a는 개수가 아닌 금액인데 k <= a 까지 for문을 돌리면 nb가 음수인 상태에서 답을 구할 수도 있습니다.

nb가 음수이면 답이 없는건데..노답노답.. 내 설명도 노답..ㅠㅠ

'for(int k=0; k <= a; k++)'로 해놓고

3 20 4 해보세요.

8 -1

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

문제

문제

출처

ICPC

7481 ATM놀이 틀렸다고 나오는데 무엇이 잘못된 걸까요?

nersery 7년 전 0

nivea50 7년 전 1

nersery 7년 전 0

nivea50 7년 전 1

nersery 7년 전 0

nivea50 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말