티스토리 뷰
#include <string>
#include <vector>
#include <cmath>
using namespace std;
bool check(long long idx, int n)
{
if(n == 0) return 1;
long long size = pow(5, n); //5제곱씩 증가
if(idx/(size/5) == 2) return 0; //인덱스가 가운데인지 체크 (무조건 0)
return check(idx%(size/5), n-1);
}
int solution(int n, long long l, long long r) {
int answer = 0;
for(long long i=l-1; i<r; i++)
{
if(check(i, n)) answer++;
}
return answer;
}
먼저 규칙을 살펴보면 가운데는 무조건 0인 것을 알 수 있다.
따라서 이를 토대로 재귀를 통해 n 값을 줄여가며 블록을 5단위로 자르고 자른 블록에 대해서도 체크한다.
재귀에는 현재 인덱스와 총 크기인 n을 넘겨주게 된다.
기본적으로 규칙에 따라 n=0 일때는 1이다.
그리고 우선 n에 대한 전체 사이즈를 구해준다.
해당 사이즐르 토대로 먼저 5로 나누어 블록의 개수를 체크하고, idx에서 이를 나누어 인덱스가 몇번 째 블록인지 체크한다.
만약 해당 값이 2라면 전체 블록의 개수가 무조건 5개이므로, 가운데에 해당한다. (0, 1, 2, 3, 4)
따라서 해당의 경우 무조건 0이기에 0을 리턴한다.
만약 가운데가 아니라면 해당 블록의 나머지를 탐색할 필요가 있다.
따라서 해당 블록을 기준으로 다시 체크를 하게 되며, 이 경우 n-1에 해당한다.
이를 토대로 위 과정을 반복하며, 가운데이면 그대로 0을 반환 아니라면 또 5개로 나눈 블록의 각 블록을 대상으로 탐색한다.
'프로그래머스 > 2레벨' 카테고리의 다른 글
[프로그래머스 2레벨] 카카오프렌즈 컬러링북 (C++) (0) | 2025.06.09 |
---|---|
[프로그래머스 2레벨] 충돌위험 찾기 (C++) (0) | 2025.06.08 |
[프로그래머스 2레벨] 완전범죄 (C++) (0) | 2025.06.05 |
[프로그래머스 2레벨] 빛의 경로 사이클 (C++) (0) | 2025.06.02 |
[프로그래머스 2레벨] 양궁대회 (C++) (0) | 2025.06.01 |