쌉쌀한 무화과의 개발로그

[문제]

N!의 값을 계산한 후에, 0이 아닌 가장 낮은 자리 수를 구하시오.

예를 들어, 4! = 24 이기 때문에, 0이 아닌 가장 낮은 자리 수는 4이다. 또, 5! = 120이기 때문에, 0이 아닌 가장 낮은 자리 수는 2 이다.

​

[입력]

첫째 줄에 N이 주어진다. N은 20,000보다 작거나 같은 자연수 이다.

​

[출력]

첫째 줄에 N!의 0이 아닌 마지막 자리수를 출력한다.

​

[예제]

>문제 풀이

예전에 틀렸던 문제를 다시 풀어보았습니다.

실버라더니 어려웠던 문제...

​

가끔 참고하는 블로그인데, 이번에도 도움을 받았습니다.

설명을 정말 잘 해놓으셨어요..bb

참고한 블로그 링크: https://steady-coding.tistory.com/322

위의 블로그에 너무 잘 정리되어있기 때문에 이번 포스팅은 제가 이해한 내용과 흐름을 위주로 추후에 다시 보기 위해 작성하겠습니다.

​

먼저 이 문제는 N!에 대해 0을 제외한 마지막 자릿수를 구하는 문제입니다.

입력되는 N의 범위가 무려 20,000 까지기 때문에 무작정 for문을 돌리면 시간초과가 일어납니다.

그래서 이 문제는 dp로 풀게 되었는데, 아래의 로직을 읽어보다 보면 왜 dp로 풀었는지 이해가 될 것입니다.

​

그래서 factorial의 계산에 대해 생각해 볼 필요가 있는데요.

먼저 끝자리에 0이 생기는 조건에 대해 생각해보면, 10의 제곱수를 곱하게 될 경우 끝자리에 0이 붙게 됩니다. 즉 2와 5의 조합에 따라 0이 생긴다고 보면되죠.

​

15!

= (1 x 2 x 3 x 4 x 5) x (6 x 7 x 8 x 9 x 10) x (11 x 12 x 13 x 14 x 15)

5의 배수를 앞으로 모아줍니다.

= (5 x 10 x 15) x (1 x 2 x 3 x 4) x (6 x 7 x 8 x 9) x (11 x 12 x 13 x 14)

​

뒤에 형광펜으로 색칠된 부분의 digit은 모두 4인것을 알 수 있습니다.

왜냐면 끝자리 기준으로

1 x 3 = 3, 2 x 4 = 8 >> digit= 4

7 x 9 =63, 6 x 8 =48 >> digit= 4

따라서 끝자리가 1, 2, 3, 4인 묶음이든, 6, 7, 8, 9인 묶음이든 0이 아닌 마지막 수는 4가 나옵니다.

​

= (5 x 10 x 15) x (1 x 2 x 3 x 4) x (6 x 7 x 8 x 9) x (11 x 12 x 13 x 14)

= 5^3 x 6 x 2^2 x 2^2 x 2^2

이제 0을 만들어내는 10을 없애주기 위해 2와 5를 조합해줍니다.

= 10^3 x 6 x 2^3 //10은 앞서 말했듯 끝자리 수에 영향 없는 0만 만들어주기 때문에

= 6 x 2^3

= 3! x 2^3

​

∴ N에 대해서 위의 방식대로 정리하게 되면

= A! x 2^p 의 구조가 나오게 됩니다.

우리는 이제 이 구조로 끝자리를 구할 수 있습니다.

​

이제 dp를 어떻게 적용시킬지 알아봅시다.

위의 식을 좀 더 정리해볼건데요.

각 숫자의 끝자리를 dp[] 배열에 담는다고 했을 때, 3!의 끝자리는 dp[3]에 담겨있겠죠?

그리고 2의 제곱수 같은 경우에는 끝자리가 2^1=2, 2^2=4, 2^3= 8, 2^4=6 이 반복됩니다.

즉, (dp[3] x 8)%10 이 15!의 0이 아닌 마지막 자릿수 입니다.

​

그렇다면 17!은 어떻게 구할 수 있을까요?

17!= dp[15] x 16 x 17

= dp[15] x 6 x 7

​

즉, N보다 작은 5의 배수의(=temp) dp값을 기준으로 temp+1~ N까지의 수를 곱해주면서 %10을 해주면 구할 수 있습니다.

​

​

* 팩토리얼 계산해주는 사이트 링크 입니다. 참고하세요~

https://ko.numberempire.com/factorialcalculator.php

>전체 코드

import java.util.Scanner;

public class Main {
	
	public static void main(String [] args) {
		int N, temp, dp[];
		
		Scanner scan= new Scanner(System.in);
		
		N= scan.nextInt();
		dp= new int[N+1];
		
		//2^n digit: 2 4 6 8
		dp[1]= 1;
		dp[2]= 2;
		dp[3]= 6;
		dp[4]= 4;
		
		for(int i=5; i<=N; i++) {
			if(i%5==0) {
				temp= i/5;
				dp[i]= (dp[temp]*(int)Math.pow(2, temp%4))%10;
			}else{
				temp= (i/5)*5;
				dp[i]=dp[temp];
				for(int j=temp+1; j<=i; j++) {
					dp[i]=dp[i]*j%10;
				}
			}
		}//end for
		
		System.out.println(dp[N]);
	}	
}

https://www.acmicpc.net/problem/2553

[문제]

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

[입력]

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

[출력]

첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

[예제]

>문제 풀이

말로만 듣던 다익스트라 알고리즘을 이용하여 풀어보았습니다.

*다익스트라 알고리즘을 풀기 위해서는 우선순위 큐에 대해서도 알아야하는데, 오래전에(?) 몇문제 안풀었더니 개념이 잘 기억이 안나더라고요... 그래서 힙 자료구조, 우선순위 큐 부터 공부하고 다익스트라 알고리즘을 이해하느라 좀 오래걸렸습니다.

**공부하기 위해 참고한 링크는(힙, 우선순위 큐, 다익스트라 알고리즘) 글 가장 아래에 달아놓겠습니다.

다익스트라 알고리즘은 음의 간선을 포함하지 않을 때 사용할 수 있는데, 이 글에서 가중치 w의 범위가 10 이하의 자연수라고 했으므로 사용 가능합니다.

main

* 초반에 가중치 값의 배열인 distance[]의 모든 값을 -1로 초기화 해줍니다.

* dijkstra 를 돌리고 나서도 distance[]값이 -1인 정점은 "INF"를 출력해줍니다.

dijkstra

우선순위에 시작지점을 offer

시작지점의 가중치 값= 0

**우선순위 큐가 빌 때까지 반복

1. 출발 정점에 연결되어 있는 정점들의 가중치 값을 넣어줍니다.

2. 방문한적이 없으면:

1. 방문처리를 해주고
2. 현재 정점을 기준으로 연결된 정점들 중에 가중치가 작은 포인트 부터 가중치 값들을 업데이트 해줍니다.
   연결된 정점 i의 가중치 값= min( 정점 i의 가중치 값, 현재 정점의 가중치 값+ 연결된 간선의 가중치 값);
3. 업데이트 후 정점 i를 우선순위 큐에 넣어줍니다.

문제를 풀기위해 참고한 글: https://jellyinghead.tistory.com/78

>전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	static int distance[];
	static LinkedList<Point> list[];
	static boolean visited[];
	
	public static void main(String [] args) throws IOException {
		int V, E, K, u, v, w;
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st= new StringTokenizer(br.readLine());
		
		V= Integer.parseInt(st.nextToken());
		E= Integer.parseInt(st.nextToken());
		K= Integer.parseInt(br.readLine());
		
		distance= new int[V+1];
		list= new LinkedList[V+1];
		visited= new boolean[V+1];
		
		Arrays.fill(distance, -1);
		for(int i=1; i<=V; i++) {
			list[i]= new LinkedList<>();
		}
		
		//입력
		for(int i=0; i<E; i++) {
			st = new StringTokenizer(br.readLine());
            u = Integer.parseInt(st.nextToken());
            v = Integer.parseInt(st.nextToken());
            w = Integer.parseInt(st.nextToken());
            list[u].add(new Point(v, w));
		}
		
		dijkstra(K);
		
		//출력
		StringBuilder sb= new StringBuilder();
		
		for(int i=1; i<=V; i++) {
			if(distance[i]==-1) sb.append("INF\n");
			else sb.append(distance[i]+"\n");
		}
		System.out.print(sb.toString());
		br.close();
		
    }//main
	
	public static void dijkstra(int start) {
		PriorityQueue<Point> pq= new PriorityQueue<>();
		Point now;
		
		pq.offer(new Point(start, 0));
		distance[start]=0;
		
		while(!pq.isEmpty()) {
			now= pq.poll();
			
			if(visited[now.end]) continue;
			visited[now.end]= true;
			for(Point next: list[now.end]) {
				if(distance[next.end]==-1||distance[next.end]>distance[now.end] + next.weight) {
					distance[next.end]= distance[now.end] + next.weight;
					pq.offer(new Point(next.end, distance[next.end]));
				}
			}
		}
	}
	
	//정점 클래스
	static	class Point implements Comparable<Point>{
		int end, weight;
			
		public Point(int end, int weight) {
			this.end= end;
			this.weight= weight;
		}
		public int compareTo(Point p) {
			return weight - p.weight;
		}
	}
}

https://www.acmicpc.net/problem/1753

**참고한 링크)

https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

https://velog.io/@gillog/Java-Priority-Queue%EC%9A%B0%EC%84%A0-%EC%88%9C%EC%9C%84-%ED%81%90

https://m.blog.naver.com/ndb796/221234424646

[문제]

상근이는 창고에서 링 N개를 발견했다. 상근이는 각각의 링이 앞에 있는 링과 뒤에 있는 링과 접하도록 바닥에 내려놓았다.

상근이는 첫 번째 링을 돌리기 시작했고, 나머지 링도 같이 돌아간다는 사실을 발견했다. 나머지 링은 첫 번째 링 보다 빠르게 돌아가기도 했고, 느리게 돌아가기도 했다. 이렇게 링을 돌리다 보니 첫 번째 링을 한 바퀴 돌리면, 나머지 링은 몇 바퀴 도는지 궁금해졌다.

링의 반지름이 주어진다. 이때, 첫 번째 링을 한 바퀴 돌리면, 나머지 링은 몇 바퀴 돌아가는지 구하는 프로그램을 작성하시오.

[입력]

첫째 줄에 링의 개수 N이 주어진다. (3 ≤ N ≤ 100)

다음 줄에는 링의 반지름이 상근이가 바닥에 놓은 순서대로 주어진다. 반지름은 1과 1000를 포함하는 사이의 자연수이다.

[출력]

출력은 총 N-1줄을 해야 한다. 첫 번째 링을 제외한 각각의 링에 대해서, 첫 번째 링을 한 바퀴 돌리면 그 링은 몇 바퀴 도는지 기약 분수 형태 A/B로 출력한다.

[예제]

>문제 풀이

최대공약수로 나눠서 기약분수를 출력해주면 됩니다.

>전체 코드

import java.util.*;

public class Main {
	
	public static void main(String [] args) {
		int N, gcd, arr[][];
		
		Scanner scan= new Scanner(System.in);
		
		N= scan.nextInt();
		arr= new int[N][2];
		
		arr[0][0]= scan.nextInt();
		for(int i=1; i<N; i++) {
			arr[i][0]= scan.nextInt();
			gcd=gcd(arr[0][0], arr[i][0]);
			arr[i][0]/=gcd; //분자
			arr[i][1]=arr[0][0]/gcd; //분모
		}
		
		for(int i=1; i<N; i++) {
			System.out.println(arr[i][1]+"/"+arr[i][0]);
		}
    }//main
	
	public static int gcd(int a, int b) {
		int mod;
		
		mod=a>b?a%b:b%a;
		if(mod==0) {
			return a<b?a:b;
		}
		return gcd(a<b?a:b, mod);
	}
}

https://www.acmicpc.net/problem/3036

[문제]

피보나치 비스무리한 수열은 f(n) = f(n-1) + f(n-3)인 수열이다. f(1) = f(2) = f(3) = 1이며 피보나치 비스무리한 수열을 나열하면 다음과 같다.

1, 1, 1, 2, 3, 4, 6, 9, 13, 19, ...

자연수 n을 입력받아 n번째 피보나치 비스무리한 수열을 구해보자!

[입력]

자연수 n(1<=n<=116)이 주어진다.

[출력]

n번째 피보나치 비스무리한 수를 출력한다.

[예제]

>문제 풀이

 예전에 틀렸던 문제가 몇 개 있길래 뭘 틀렸나 싶어서 다시 풀어보려고 한다.

오늘 문제는 쉬웠었는데, 아마 풀다가 말았던게 아닌가 싶다.

arr[1], arr[2], arr[3]=1 미리 넣어주고(단 입력값에 따라 대입 처리를 해줘야한다.)

arr[i]= arr[i-3]+arr[i-1]; 을 for문 돌려주면 된다.

>전체 코드

import java.util.*;

public class Main {
	
	public static void main(String [] args) {
		int N;
		long arr[];
		
		Scanner scan= new Scanner(System.in);
		
		N= scan.nextInt();
		arr= new long[N+1];
		
		arr[1]=1;
		if(N>1) arr[2]=1;
		if(N>2) arr[3]=1;
		for(int i=4; i<=N; i++) {
			arr[i]=arr[i-3]+arr[i-1];
		}
		
		System.out.println(arr[N]);
        
    }//main	
}

https://www.acmicpc.net/problem/14495

[문제]

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.

X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

[입력]

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.

[출력]

첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.

[제한]

• 1 ≤ N ≤ 1,000,000
• -109 ≤ Xi ≤ 109

[예제]

>문제 풀이

정렬하는 방법과 hashmap 사용할 줄만 알면 쉬운 문제였다.

(근데 hashmap 딱 한번 써보고 안써서 까먹어서 다시 찾아봄..ㅎㅎ;)

<로직>

1. N, arr[] 입력 받고
2. arr_v= arr.clone(); // arr_v[] 배열에다가 깊은 복사로 붙여넣는다.
3. arr.sort
4. N만큼 반복문을 돌리며
   : arr값을 중복되지 않게 hashmap에 넣는다.
5. N만큼 반복문을 돌리며
   : StringBuilder sb에다가 hashmap에서 키값이 arr_v인 value를 붙여준다.(append)
6. sb.toString()을 출력한다.

>전체 코드

import java.util.*;

public class Main {
	
	public static void main(String [] args) {
		int N, before, arr[], arr_v[];
		
		Scanner scan= new Scanner(System.in);
		
                //입력받기
		N= scan.nextInt();
		arr= new int[N];
		arr_v= new int[N];
		HashMap<Integer, Integer> map= new HashMap<>();
		
		for(int i=0; i<N; i++) {
			arr[i]= scan.nextInt();
		}
        
		arr_v= arr.clone(); //arr를 arr_v로 (깊은)복사
		Arrays.sort(arr); //정렬
		
		before= (int)Math.pow(10, 9)+1;
		for(int i=0, j=0; i<N; i++) {
			if(before!=arr[i]) { //중복아닌 값만
				map.put(arr[i], j++);//map에 저장
				before=arr[i];
			}
		}
		
		StringBuilder sb= new StringBuilder();
		for(int i=0; i<N; i++) {
			sb.append(map.get(arr_v[i])+" "); //arr_v값을 키로 가진 map을 get
		}
		System.out.println(sb.toString()); //출력~~
		
    }//end	
}

https://www.acmicpc.net/problem/18870