algospot 어린이날 (문제 ID: CHILDRENDAY) c++

알고스팟 문제 링크: https://algospot.com/judge/problem/read/CHILDRENDAY

algospot.com :: CHILDRENDAY

문자열로 주어진 특정 십진수(0~9)로만 장난감 갯수를 확보할 수 있다.

장난감을 n명의 아이들에게 나눠주는데 그 중 m명은 같은 개수의 장난감을 받으면 삐지므로 한 개 더 주려 한다.

위 조건을 만족하면서 가능한 적은 수의 장난감의 갯수 c를 계산하는 문제이다.

 

문제에 주어진 c에 대한 조건을 정리하면 다음과 같다.

1. n+m 이상이어야 한다.

2. n으로 나눈 나머지가 m이어야 한다.

3. d에 포함된 숫자들로만 구성되어 있어야 한다.

먼저 3번 조건을 만족하는 숫자들 중에서 2번을 만족하는 경우를 계산하는 방법을 생각해보면,

c의 뒤에 숫자 x를 붙여나가는 방식으로 c를 확장한다면 ((c mod n)*10+x) mod n = (c*10+x) mod n 이므로 c를 n으로 나눈 나머지가 m인 최소 숫자를 찾을 수 있다.

이때 주의할 점은 n+m이상인 조건도 만족시켜야 하므로 n+m미만인 나머지값 정점이랑 n+m이상인 나머지값 정점을 구분해야 한다.

 

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/29.%20BFS/CHILDRENDAY.cpp

GitHub - sbl133/JongmanBook

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2