SSAFY 합격의 중심, 알고리즘잡스입니다.
성원 감사 CT 퀴즈 이벤트에 참여해주심에 감사드립니다.
<알잡이의 마지막 정리> 문제
추후 재업로드 예정
(기존 수강생은 수강생 전용 토론방 참고)
<알잡이의 마지막 정리> 풀이
예시로 n = 82355, k = 3인 상황을 보겠습니다.
일의 자리에 3이 등장하는 경우를 보면 아래와 같습니다.
3, 13, 23, 33, 43, 53, ... 82353
십의 자리에 3이 등장하는 경우를 보면 아래와 같습니다.
30~39, 130~139, 230~239, ... 82330~82339
백의 자리에 3이 등장하는 경우를 보면 아래와 같습니다.
300~399, 1300~1399, ... 82300~82355
천의 자리에 3이 등장하는 경우를 보면 아래와 같습니다.
3000~3999, 1300~1399, ... 73000~73999
만의 자리에 3이 등장하는 경우를 보면 아래와 같습니다.
30000~39999
규칙을 찾아봅시다.
1. 일의 자리는 하나씩, 십의 자리는 10개씩, 백의 자리는 100개씩, 천의 자리는 1000개씩 연달아 등장합니다. 이 단위 하나를 세트라고 표현하겠습니다.
2. 어떤 자리의 수가 k보다 크다면 그 앞까지 자른 수 + 1 만큼의 세트가, k보다 작거나 같다면 그 앞까지 자른 수만큼의 세트가 만들어집니다. 예를들어 위 예시에서 십의 자리를 생각해보면 30~39, 130~139, ... 82330~82339로 총 824개의 세트가 생깁니다. 이는 82355의 십의 자리 앞에서 수를 자른 823에 1을 더한 수입니다.
3. 어떤 자리의 수가 k와 같다면 세트와 별개로 그 자리의 뒤에 있는 수 + 1만큼의 k가 존재합니다. 예를들어 위 예시에서 백의 자리는 89개의 세트가 있고, 그 뒤에 82300~82355까지 총 56개의 3이 더 존재합니다. 이는 82355의 백의 자리에서 자른 뒷부분 55에 1을 더한 수입니다.
따라서 아래와 같은 방법으로 답을 구할 수 있습니다.
n = 82355 이라면 k와 상관 없이 일의 자리에는 최소 8235개의 세트가, 십의 자리에는 최소 823개의 세트가, 백의 자리에는 최소 82개의 세트가, 천의 자리에는 최소 8개의 세트가 존재하기 때문에 8235 + 8230 + 8200 + 8000을 구해둡니다.
만약 k = 3이라면 3보다 큰 자리들, 만의 자리, 십의 자리, 일의 자리에 한 세트씩 더 생깁니다. 따라서 10000 + 10 + 1을 더해줍니다.
마지막으로 백의 자리가 k와 같은 3이므로 그 뒤에 있는 55 + 1 = 56을 정답에 더해줍니다.
알잡이가 생각한 정답을 쉽게 구하는 방법은 위와 같습니다.
<알잡이의 마지막 정리> 정답
1) 19
2) 284
3) 15597
4) 38203
5) 539768
SSAFY 합격의 중심, 알고리즘잡스입니다.
성원 감사 CT 퀴즈 이벤트에 참여해주심에 감사드립니다.
<알잡이의 마지막 정리> 문제
추후 재업로드 예정
(기존 수강생은 수강생 전용 토론방 참고)
<알잡이의 마지막 정리> 풀이
예시로 n = 82355, k = 3인 상황을 보겠습니다.
일의 자리에 3이 등장하는 경우를 보면 아래와 같습니다.
3, 13, 23, 33, 43, 53, ... 82353
십의 자리에 3이 등장하는 경우를 보면 아래와 같습니다.
30~39, 130~139, 230~239, ... 82330~82339
백의 자리에 3이 등장하는 경우를 보면 아래와 같습니다.
300~399, 1300~1399, ... 82300~82355
천의 자리에 3이 등장하는 경우를 보면 아래와 같습니다.
3000~3999, 1300~1399, ... 73000~73999
만의 자리에 3이 등장하는 경우를 보면 아래와 같습니다.
30000~39999
규칙을 찾아봅시다.
1. 일의 자리는 하나씩, 십의 자리는 10개씩, 백의 자리는 100개씩, 천의 자리는 1000개씩 연달아 등장합니다. 이 단위 하나를 세트라고 표현하겠습니다.
2. 어떤 자리의 수가 k보다 크다면 그 앞까지 자른 수 + 1 만큼의 세트가, k보다 작거나 같다면 그 앞까지 자른 수만큼의 세트가 만들어집니다. 예를들어 위 예시에서 십의 자리를 생각해보면 30~39, 130~139, ... 82330~82339로 총 824개의 세트가 생깁니다. 이는 82355의 십의 자리 앞에서 수를 자른 823에 1을 더한 수입니다.
3. 어떤 자리의 수가 k와 같다면 세트와 별개로 그 자리의 뒤에 있는 수 + 1만큼의 k가 존재합니다. 예를들어 위 예시에서 백의 자리는 89개의 세트가 있고, 그 뒤에 82300~82355까지 총 56개의 3이 더 존재합니다. 이는 82355의 백의 자리에서 자른 뒷부분 55에 1을 더한 수입니다.
따라서 아래와 같은 방법으로 답을 구할 수 있습니다.
n = 82355 이라면 k와 상관 없이 일의 자리에는 최소 8235개의 세트가, 십의 자리에는 최소 823개의 세트가, 백의 자리에는 최소 82개의 세트가, 천의 자리에는 최소 8개의 세트가 존재하기 때문에 8235 + 8230 + 8200 + 8000을 구해둡니다.
만약 k = 3이라면 3보다 큰 자리들, 만의 자리, 십의 자리, 일의 자리에 한 세트씩 더 생깁니다. 따라서 10000 + 10 + 1을 더해줍니다.
마지막으로 백의 자리가 k와 같은 3이므로 그 뒤에 있는 55 + 1 = 56을 정답에 더해줍니다.
알잡이가 생각한 정답을 쉽게 구하는 방법은 위와 같습니다.
<알잡이의 마지막 정리> 정답
1) 19
2) 284
3) 15597
4) 38203
5) 539768