글 읽기 - [C++] 뭔가 깔끔하게 풀고 있는 느낌이 안 드네요

lucete171 3년 전 0

(접근 방법)

어떤 수를 소인수분해 하였을때 n=(a1^n1) * (a2^n2) * ... (aX^nX)으로 나타난다고 할 떄

진짜 약수 리스트에서 a1^n1, a2^n2,...,aX^nX의 값들만을 남기고 그들을 곱하는 방법으로 접근했습니다

(풀이 방법)

S1) 입력받은 값들을 arr에 저장하고 그 중 소수들을 tmp1에 저장

S2) arr중에서 tmp1을 이용하여 합성수들을 제외 단, 4,9,25와 같은 소인수분해하였을 때 소수가 1개인 경우는 남기고 tmp2에 저장

S3) tmp2에서 각 소수에 따른? 가장큰 수들을 남긴다 ~ 자세한 설명은 소스 쪽에 있습니다

S4) if tmp1의 원소가 1개 인 경우: tmp1의 원소와 tmp2의 마지막 원소를 곱하고 result에 저장- result = tmp1[0] * tmp2[k2-1]

else : tmp2의 원소들을 모두 곱하고 result 에 저장

S5) result를 출력

(질문)

Q1) 이 소스를 돌리면 틀렸습니다 가 나오는 데 그 반례를 아직 구하지 못했습니다 반례가 뭐가 있을까요?

Q2) 45~50 에서 cnt 가 1을 넘는 순간 다음i로 넘어가고 j를 초기화 시키는 방법은 없을까요

(애초에 cnt가 1이 넘는 순간 합성수인건 확실한 데 계속 카운트하고 있으니 시간을 낭비하는 것 같아서요)

#include <stdio.h>

int test(int p){
	int cnt=0;
	for(int i=2;(i*i)<=p;i++)
	{
		if(p%i==0)
		{
			cnt++;
			return 0;
			break;
		}
	}
	if(cnt==0)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

int main()
{
	int n;
	scanf("%d",&n);
	int arr[n];
	int tmp1[n]={0};
	int tmp2[n]={0};
	int k1=0;
    
    //1
	for(int i=0;i<n;i++)
	{
		scanf("%d",&arr[i]);
		if(test(arr[i])==1)
		{
			tmp1[k1++]=arr[i];
		}
	}
    
    //2
	int k2=0;
	for(int i=0;i<n;i++)
	{
		int cnt=0;
		for(int j=0;j<k1;j++)
		{
			if(arr[i]%tmp1[j]==0)
			{
				cnt++;
			}
		}
		if(cnt==1)
		{
			tmp2[k2++]=arr[i];
		}
	}
    
	//3
	//tmp2의 원소들끼리 서로 나누어지면 나누는 쪽의 원소를 1로 바꾸고 넘어간다
    //예를 들어 tmp2에 2 3 4 9가 남았다고 할 때
    //아래의 과정을 거치면 1 1 4 9가 남는다
	for(int i=0;i<k2;i++)
	{
		for(int j=i+1;j<k2;j++)
		{
			if(tmp2[j]%tmp2[i]==0)
			{
				tmp2[i]=1;
			}
			if(tmp2[i]==1)
			{
				i++;
				j=i+1;
			}
		}
	}
    
	//4
	int result=1;
	if(k1==1)
	{
		int max=0;
		for(int i=0;i<k2;i++)
		{
			if(max<tmp2[i])
			{
				max=tmp2[i];
			}
		}
		result=tmp1[0]*max;
	}
	else
	{
		for(int i=0;i<k2;i++)
		{
			result*=tmp2[i];
		}
	}
    
    //5
	printf("%d",result);
	return 0;
}

lucete171 3년 전 0

약수를 크기 순으로 입력하는 게 아니군요...일단 이거부터 해결해야 3번 과정이 정확하게 돌아가겠군요

lucete171 3년 전 0

이렇게 비꿔서 결국 풀기는 했는데 Q2는 아직 해결 안됐습니다

	for(int i=0;i<k2;i++)
	{
		for(int j=i+1;j<k2;j++)
		{
			if(tmp2[i]%tmp2[j]==0)
			{
				tmp2[j]=1;
			}
			else if(tmp2[j]%tmp2[i]==0)
			{
				tmp2[i]=1;
			}
		}
	}

lucete171 3년 전 0

for문 공부 좀 더 해야겠네요

쉽게 해결했습니다ㅜ

if(cnt>1)
    break;
    

댓글을 작성하려면 로그인해야 합니다.