백준 27231번 2023년이 기대되는 이유

문제 설명

이번 문제는 정수 n이 주어졌을 경우, n의 자리수 사이사이에 0개 이상의 +기호를 넣어서 계산했을 때, 그 값이 각 자리수를 m제곱한 수들의 합과 같아지는 m의 개수를 구하는 문제입니다.

 

문제 풀이

아이디어

조합

n의 자리수 사이사이에 +기호가 들어갈 수 있는 경우의 수를 구할 경우 조합을 사용합니다.

 

이분 탐색

자리수 사이사이에 0개 이상의 +기호를 넣어서 계산한 값과 각 자리수를 m제곱한 합 중 같은 값이 있는지 비교할 경우 두 배열을 모두 순회하면서 값을 비교하는 것은 너무 많은 시간이 걸리므로, 이분탐색을 이용해 서로 같은 값이 있는지 비교해줍니다.

 

풀이

0과 1

각 자리수가 0 혹은 1만 존재할 경우, 해당 숫자의 m의 개수는 무한히 많아지므로 'Hello, BOJ 2023!'을 출력합니다.

 

+기호를 넣은 수 구하기

각 자리수 사이사이의 위치의 조합을 구한 다음, 해당 위치에 +를 넣었을 경우 만들어지는 숫자를 배열로 저장합니다.

 

같은 값이 있는지 비교

+기호를 사이사이 넣어서 만든 수를 저장하고 있는 배열에 대해, 각 자리수를 m제곱한 수들의 합이 있는지 확인합니다.

이 때, 이분 탐색을 이용하여 같은 값이 있는지 확인해줍니다.

 

 

해결

이번 문제는, 차근차근히 고민하여 해결할 수 있었습니다.

 

문제 링크 : https://www.acmicpc.net/problem/27231

27231번: 2023년이 기대되는 이유

코드 링크 : https://github.com/beomseok37/baekjoon/blob/master/new!/27231.py