[BOJ-JS] 1274번 - 커피숍1

1274번: 커피숍1 (acmicpc.net)

1274번: 커피숍1

이 문제는 얼핏 보면 간단한 시뮬레이션 문제처럼 보이는데 도대체 왜 언레일까 궁금해하면서 풀기 시작했다. 소수점 계산이 누적되면서 오차가 커져서 틀리게 되는 트릭이 섞여있을 거라고 생각하고 쫄아서 정수 계산으로 구현했는데, 아이디어는 다음과 같다.

 

• 처음에 각 항아리에 들어있는 커피 가루의 양을 계산. (a, b)에 (a * Sa, b * Sb)를 대입한다.
• 항아리에 있는 커피를 옮기는 전체 시행을 한 번 끝냈다고 하자. 이때 각 항아리에 들어있는 커피 가루의 양은 다음과 같다.
  • (a - a*(S/Sa) + b*(S/Sb), b*(Sb-S)/Sb)
• 여기서 a 항아리에 들어있는 커피 가루의 양이 줄어들었다면 멈춰야 한다. 즉, 다음이 성립해야 한다.
  • b*(S/Sb) - a*(S/Sa) >= 0, 즉, Sa * b - Sb * a >= 0
• 위의 식을 보면 a, b의 실제 값이 계산의 결과에 영향을 미치는 것이 아니라, a, b의 상대적 크기가 영향을 미친다. 이를 활용하여 한 번 커피를 옮기는 시행을 한 뒤의 a, b에 있는 커피 가루의 양을 정수로 표현하여 대입한다. 즉, 실제 커피 가루의 양이 아닌 값이 a, b에 들어있게 되지만, 결과에는 영향을 미치지 않음.
  • (a, b)를 (a * (Sa-S) * Sb + b * Sa * S, b * (Sb - S) * Sa)로 바꿈

 

하지만 위의 과정을 코드로 바꾸기 전에 몇 가지 체크해야 하는 포인트가 있다.

글 읽기 - 혹시라도 이 문제를 해결하고 싶으신 분들을 위해 조건 정리해두겠습니다.. (acmicpc.net)

글 읽기 - 혹시라도 이 문제를 해결하고 싶으신 분들을 위해 조건 정리해두겠습니다..

• A에서 한 잔을 따르지 못하면 종료. 즉, Sa < S 조건을 체크해야 한다.
• B에서 A로 한 잔을 옮기지 못해도 종료. 즉, Sb < S 조건을 체크해야 한다.
• A에서 한 잔을 마시고 B에서 A로 옮기지 못할 경우 그래도 한 잔은 마신 것이다.
• '현재 마시는 커피보다 진한 커피를 같은 날 마셨었다면 현재 마시는 커피의 맛을 느끼지 못한다.' 즉, 농도가 같아도 상관 없다.
• '50잔을 넘어가는 경우엔 “gg”를 큰 따옴표 없이 출력한다.' 여기서의 50잔은 10진수 기준이고, 넘어가는 경우 이와 같이 출력해야 하므로 초과 조건으로 생각.
• 16진수로 표현한 수는 알파벳 대문자로 출력. js에서는 toString(16)을 쓰면 소문자로 바뀌어서 이것도 체크해주어야 한다.

다른 분들이 기여한 것을 보니 큰 수 연산은 필요 없었던것 같다. 그럴 경우 간단한 시뮬레이션 문제가 되므로, 난이도는 다른 분들이 책정한 것과 같이 브1로 기여. 하지만 solvedac 공식 계정이 난해한 지문으로 인해 난이도를 매길 수 없다고 기여하고 standard가 되어버려서 현재는 언레로 책정되어 있는 것으로 보인다.

[a,b,Sa,Sb,S]=(0+require('fs').readFileSync(0)).split(/\s|\n/).map(BigInt)
i=0
a*=Sa
b*=Sb
while(i<51){
  if(Sa<S)break
  i++
  if(Sb<S)break
  if(Sa*b-Sb*a<0)break
  aa=a*(Sa-S)*Sb+b*Sa*S
  bb=b*(Sb-S)*Sa
  a=aa
  b=bb
}
console.log((i>50||i<=0)?'gg':i.toString(16).toUpperCase())