푸른다리컵: 특수한 질수 늑골(점차적으로 낮은 위치를 없애도 질수의 수, 특수질수) 귀속해법

7001 단어 블루 브리지 컵

푸른다리컵: 특수한 질수 늑골(점차적으로 낮은 위치를 없애도 질수의 수, 특수질수) 귀속해법


문제 설명


농민 존 암소는 항상 가장 좋은 갈비뼈가 생긴다.너는 농민 존과 미국 농업부가 갈비뼈 하나하나에 표시한 숫자를 통해 그것들을 알아볼 수 있다.농민 존은 그가 구매자에게 판매한 것이 진정한 질수 갈비뼈라고 확신했다. 왜냐하면 오른쪽부터 갈비뼈를 자르기 시작했기 때문이다. 매번 남은 갈비뼈의 숫자는 모두 질수를 구성하기 때문이다.
예를 들어 네 개의 갈비뼈가 있는 숫자는 각각 7331이다. 그러면 전체 갈비뼈의 숫자 7331은 질수이다.세 개의 갈비뼈 733은 질수이다.두 갈비뼈 73은 질수이다.물론 마지막 갈비뼈 7도 질수다.7331은 길이 4의 특수 질수라고 불린다.
주어진 갈비뼈의 수량 N(1<=N<=8)에 대한 프로그램을 작성하여 모든 특수한 질량을 구합니다.숫자 1은 하나의 질수로 간주되지 않는다.입력 형식은 별도의 줄에 N을 포함합니다.출력 형식은 줄마다 길이가 N인 특수 질수를 순서대로 출력합니다.샘플 입력
사
샘플 출력
2333
2339
2393
2399
2939
3119
3137
3733
3739
3793
3797
5939
7193
7331
7333
7393

생각


제목 주의: ↓
예를 들어 네 개의 갈비뼈가 있는 숫자는 각각 7331이다. 그러면 전체 갈비뼈의 숫자 7331은 질수이다.세 개의 갈비뼈 733은 질수이다.두 갈비뼈 73은 질수이다.물론 마지막 갈비뼈 7도 질수다.7331은 길이 4의 특수 질수라고 불린다.
처음에 내가 모든 수의 조합을 궁리한 줄 알았는데 길이가 4인 것부터 판단하고 길이가 1인 것을 보았다. 즉, 판단 7331, 판단 733, 판단 73, 판단 7이다. 나중에 이것이 시간을 소모하는 방법이라는 것을 발견했다
  • 짧은 숫자부터 판단해야 효과적으로 가지를 자를 수 있다

    • 예를 들어 7 이 질수인지 아닌지를 먼저 판단하고 73 을 판단하고 733 을 판단한다. 마지막은 7331이다. 이때 나는 제목이 왜 오른쪽에서 잘라야 하는지 알았다. 판단의 순서와 진위의 규칙이 일치한다.
  • 만약에 현재 숫자 x가 질수라면 x를 10으로 곱하고 임의의 숫자를 더해서 판단한다

    • 이렇게 하면 매번 귀속되어 들어가는 x가 모두 질수이고 효과적인 가지치기를 보장할 수 있다

    코드

    #include 
#include 

using namespace std;

int n;
int ans[114514];

int prime(int x)
{
	if(x == 1)
	{
		return 0;
	}
	
	for(int i=2; i<=(int)sqrt(x); i++)
	{
		if(x%i == 0)
		{
			return 0;
		}
	}
	
	return 1;
}

void dfs(int x, int len)
{
	if(len > n)
	{
		cout<<x<<endl;	
	}
	else
	{
		for(int i=1; i<=9; i++)
		{
			if(prime(x*10 + i))
			{
				dfs(x*10+i, len+1);
			}
		}
	}
}

int main()
{
	cin>>n;
	
	dfs(0, 1);
	
	return 0;
}
    Unity에서 Observer를 사용하기 위해 노력하는 이야기입니다.
    워터마크 이미지가 Backblaze B2 Bucket에 자동으로 업로드됩니다.

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage