수
백준 링크
0부터 9까지 K가지의 숫자를 한 번씩만 사용하여 만들 수 있는 수
중 아래 조건을 모두 만족하는 수들의 개수를 구해보자.
입력 (주어지는 것)
K (0~9중에서 K가지 숫자를 이용해 수를 만든다) , M (만든수를 M으로 나누어본다)
조건
- 서로 다른 두개의 소수의 합으로 나타낼 수 있음
- M으로 나누어 떨어지지 않을때까지 나눈 수가 두개의 소수의 곱이다 (두개의 소수가 같아도된다.)
=> 서로 다른 두개의 소수의 합으로 나타 낼 수 있으면서도 M으로 나눈 값이 두개의 소수의 곱
예) K가 1이고 M이 11인 경우
1번 조건을 만족하는 수는 5,7,8,9
2번 조건을 만족하는 수는 4,6,9
1,2 동시 만족하는 수는 9
출력
조건을 만족하는 수의 개수
풀이
- 소수를 구한후
- 합의 배열
- 곱의 배열을 만든다.
- 시간 부족 안나도록 적절한 값을 구한다.
<실패한코드>
이코드상이라면 k=5일때 10000가 중복된 숫자를 포함하고 있음에도 불구하고 가능하게 된다.
import java.util.*;
public class Main {
public static Scanner scan =new Scanner(System.in);
public static StringBuilder sb=new StringBuilder();
public static int[] arr,arr2,arr3;
static int K,M,cnt=0;
public static void main(String[] args) {
//입력
K=scan.nextInt(); //자리 수
M=scan.nextInt(); // 나누는 수
int max=(int) Math.pow(10, K);
arr=new int[max]; // 소수 배열
arr2= new int[max]; // 두 소수의 합의 배열
arr3=new int[max]; // 두 소수의 곱의 배열
//에라토스테네스의 체로 소수구하기
arr[0]=arr[1]=1;
for(int i=2;i*i<max;i++) {
if(arr[i]==1) continue;
for(int j=i*i;j<max;j+=i) {
arr[j]=1;
}
}
//소수의 합이 체크되어 있는 배열 구하기
for(int a=2;a<max-1;a++) {
if(arr[a]==1) continue;
for(int b=a+1;b<max;b++) {
if(arr[b]==1)continue;
if(a+b>=max) continue;
arr2[a+b]=1;
}
}
//소수의 곱이 체크되어있는 배열 구하기
for(int a=2;a<max;a++) {
if(arr[a]==1) continue;
for(int b=a;b<max;b++) {
if(arr[b]==1)continue;
long num=(long)a*(long)b;
if(num>=max) continue;
arr3[a*b]=1;
}
}
//i : 구하려는 수
for(int i=(int)Math.pow(10,K-1);i<max;i++) {
if(arr2[i]==1) { //합으로 나타낼 수 있고
int num=i;
while(true) { //m으로 나누어 떨어질 때 까지 나눈수가 두개의 소 수의 곱인경우
if(num%M==0) {
num/=M;
}else break;
}
if(arr3[num]==1) {
cnt++;
}
}
}
System.out.print(cnt);
}
}<성공한 코드>
import java.util.*;
public class Main {
public static Scanner scan =new Scanner(System.in);
public static StringBuilder sb=new StringBuilder();
public static int[] arr,arr2,arr3,visited;
static int K,M,cnt=0;
public static void main(String[] args) {
//입력
K=scan.nextInt(); //자리 수
M=scan.nextInt(); // 나누는 수
int max=(int) Math.pow(10, K);
arr=new int[max]; // 소수 배열
arr2= new int[max]; // 두 소수의 합의 배열
arr3=new int[max]; // 두 소수의 곱의 배열
visited=new int[10];
//에라토스테네스의 체로 소수구하기
arr[0]=arr[1]=1;
for(int i=2;i*i<max;i++) {
if(arr[i]==1) continue;
for(int j=i*i;j<max;j+=i) {
arr[j]=1;
}
}
//소수의 합이 체크되어 있는 배열 구하기
for(int a=2;a<max-1;a++) {
if(arr[a]==1) continue;
for(int b=a+1;b<max;b++) {
if(arr[b]==1)continue;
if(a+b>=max) continue;
arr2[a+b]=1;
}
}
//소수의 곱이 체크되어있는 배열 구하기
for(int a=2;a<max;a++) {
if(arr[a]==1) continue;
for(int b=a;b<max;b++) {
if(arr[b]==1)continue;
long num=(long)a*(long)b;
if(num>=max) continue;
arr3[a*b]=1;
}
}
//i : 구하려는 수
for(int i=(int)Math.pow(10,K-1);i<max;i++) {
if(arr2[i]==1) { //합으로 나타낼 수 있고
int num=i;
while(true) { //m으로 나누어 떨어질 때 까지 나눈수가 두개의 소 수의 곱인경우
if(num%M==0) {
num/=M;
}else break;
}
if(arr3[num]==1) {
cnt++;
}
}
}
int ret=comb(0,0,0);
System.out.print(ret);
}
static boolean check(int val) {
while(val%M==0) val/=M;
if(arr3[val]==1) {
return true;
}
return false;
}
static int comb(int cur,int idx ,int val)
{
if(idx == K)
{
if(arr2[val] == 1&& check(val))
return 1; //조건 1,2에 모두 부합하는 경우 결과값에 +1해준다. (ret이 +1된다.)
return 0;
}
int ret = 0;
for(int i = cur ;i<=9;i++)
{
if(idx ==0 && i == 0) //맨첫자리일때는 0을 비허용한다.
continue;
if(visited[i] == 1) //방문한 숫자이면 pass
continue;
visited[i] =1 ;
ret += comb(cur ,idx+1,val*10 + i); //재귀
visited[i] = 0; //재귀 끝나고 돌아오면 다시 체크 풀어주기
}
return ret; //최종적으로 재귀를 다 돌았을 때 return된 1값이 다 더해진 ret을 return해준다. (ret=조건에 맞는 수의 개수)
}
}0~9까지의 수가 중복으로 사용되지 않도록 재귀를 통해 순열과 같은 방법으로 조건에 맞는 수를 찾는다. 주석 참고!
다음 순열
백준 링크
1~N까지의 수로 이루어진 순열이 있다.
사전순으로 다음에 오는 수열을 구하시오
입력
N과
순열
출력
입력으로 주어진 순열 다음으로 오는 순열 출력
(주어진 순열이 마지막인 경우 -1 출력)
<틀린 풀이>
시간초과
import java.util.*;
public class Main {
public static Scanner scan =new Scanner(System.in);
public static StringBuilder sb=new StringBuilder();
public static int[] arr,visited,arr3;
static int[] perm;
static int N,num=0,cnt2;
static boolean flag;
public static void main(String[] args) {
//입력
N=scan.nextInt();
arr=new int[N];
perm=new int[N];
visited=new int[N+1];
for(int i=0;i<N;i++) {
arr[i]=scan.nextInt();
}
//맨 마지막거 일때
for(int j=0;j<N;j++) {
if(arr[j]==N-j) {
cnt2++;
}
}
if(cnt2==N) {
System.out.print(-1);
}
else {
if(arr[0]<N/2) {
dfs(0);
}
else {dfs2(0);}
}
}
static void dfs(int depth) {
if(depth==N) {
//basecase
if(flag) {
for(int a=0;a<N;a++) {
System.out.print(perm[a]+" ");
}
System.exit(0);
}
int cnt=0;
for(int a=0;a<N;a++) {
if(arr[a]==perm[a]) {
cnt++;
}
}
if(cnt==N) {
flag=true;
}
return;
}
for(int i=1;i<=N;i++) {
if(visited[i]==0) { //방문하지않았다면
perm[depth]=i;
visited[i]=1;
dfs(depth+1);
visited[i]=0;
}
}
}
static void dfs2(int depth) {
if(depth==N) {
//basecase
if(flag) {
for(int a=0;a<N;a++) {
System.out.print(perm[a]+" ");
}
System.exit(0);
}
int cnt=0;
for(int a=0;a<N;a++) {
if(arr[a]==perm[a]) {
cnt++;
}
}
if(cnt==N) {
flag=true;
}
return;
}
for(int i=N;i>=1;i--) {
if(visited[i]==0) { //방문하지않았다면
perm[depth]=i;
visited[i]=1;
dfs(depth+1);
visited[i]=0;
}
}
}
}int i = 배열의 크기-1,
int j = 배열의 크기-1 일때
-
i > 0 이면서 A[i-1] < A[i]를 만족하는 카장 큰 i를 찾는다. //오름차순이 끝나는 지점
-
A[j] > A[i-1]을 만족하는 가장 큰 j를 찾는다. //내림차순일것이기때문에
-
A[i-1]과 A[j]를 swap한다.
-
A[i]부터 순열을 뒤집는다.
import java.util.*;
public class Main {
public static Scanner scan =new Scanner(System.in);
public static StringBuilder sb=new StringBuilder();
public static int[] arr,visited,arr3;
static int[] perm;
static int N,num=0,cnt2;
static boolean flag;
public static void main(String[] args) {
//입력
N=scan.nextInt();
arr=new int[N];
perm=new int[N];
visited=new int[N+1];
for(int i=0;i<N;i++) {
arr[i]=scan.nextInt();
}
if(nextperm(arr))
{
for(int i=0;i<N;i++) {
System.out.print(arr[i]+" ");
}
}
else {
System.out.print(-1);
}
}
static boolean nextperm(int[] arr) {
int i=arr.length-1;
int j=arr.length-1;
while(i>0&&arr[i-1]>=arr[i]) i--;
if(i<=0) return false;
while(arr[j]<=arr[i-1]) j--;
swap(arr,i-1,j);
j=arr.length-1;
while(i<j) {
swap(arr,i,j);
i++;
j--;
}
return true;
}
static void swap(int[] arr, int idx1, int idx2) {
int temp=arr[idx1];
arr[idx1]=arr[idx2];
arr[idx2]=temp;
}
}
남기고 싶은 개발자입니다 :>