백준 JAVA11 1033번 : 칵테일
Mention : 문제와 아이디어는 이해가 됬으나, DFS와 비율을 곱해주는 구현이 개인적으로 매우 어려운 문제였다.
- DFS, GCD, LCM을 사용해야하며, 입력값 때문에 노드 class도 만들어줘야 했다.
- 나중에 다시 한번 구현해보자🧐
칵테일
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 3123 | 809 | 640 | 29.507% |
문제
august14는 세상에서 가장 맛있는 칵테일이다. 이 칵테일을 만드는 정확한 방법은 아직 세상에 공개되지 않았지만, 들어가는 재료 N개는 공개되어 있다.
경근이는 인터넷 검색을 통해서 재료 쌍 N-1개의 비율을 알아냈고, 이 비율을 이용해서 칵테일에 들어가는 전체 재료의 비율을 알아낼 수 있다.
총 재료 쌍 N-1개의 비율이 입력으로 주어진다. 이때, 칵테일을 만드는데 필요한 각 재료의 양을 구하는 프로그램을 작성하시오. 이때, 필요한 재료의 질량을 모두 더한 값이 최소가 되어야 한다. 칵테일을 만드는 재료의 양은 정수이고, 총 질량은 0보다 커야한다.
비율은 “a b p q”와 같은 형식이고, a번 재료의 질량을 b번 재료의 질량으로 나눈 값이 p/q라는 뜻이다.
입력
첫째 줄에 august14를 만드는데 필요한 재료의 개수 N이 주어지며, N은 10보다 작거나 같은 자연수이다.
둘째 줄부터 N-1개의 줄에는 재료 쌍의 비율이 한 줄에 하나씩 주어지는데, 문제 설명에 나온 형식인 “a b p q”로 주어진다. 재료는 0번부터 N-1까지이며, a와 b는 모두 N-1보다 작거나 같은 음이 아닌 정수이다. p와 q는 9보다 작거나 같은 자연수이다.
출력
첫째 줄에 칵테일을 만드는데 필요한 각 재료의 질량을 0번 재료부터 순서대로 공백으로 구분해 출력한다.
예제 입력 1
5
4 0 1 1
4 1 3 1
4 2 5 1
4 3 7 1
예제 출력 1
105 35 21 15 105
예제 입력 2
2
0 1 6 4
예제 출력 2
3 2
예제 입력 3
3
0 1 9 8
1 2 9 8
예제 출력 3
81 72 64
예제 입력 4
4
2 3 6 8
0 1 9 3
3 0 7 5
예제 출력 4
60 20 63 84
출처
슈도 코드
N(재료개수)
Array(인접 리스트)
lcm(최소 공배수)
mass(칵테일 재료의 질량 저장 배열)
visited(DFS 탐색시 방문여부 기록 배열)
변수 초기화
for(엣지 개수 // N-1) {
인접 리스트 배열에 엣지 정보 저장하기
최소 공배수 업데이트 하기
}
0번 노드에 최소 공배수 저장하기
0번에서 DFS 탐색 수행하기
DFS를 이용해 업데이트된 mass 배열의 값들의 최소공약수(gcd) 계산하기
출력
mass 배열의 값 / gcd
유클리드 호제법 사용
gcd(a,b) {
if(b == 0)
return a
else
gcd(b, a%b) //재귀함수
}
DFS 구현함수
DFS() {
visited 배열에 현재 노드 방문 기록
현재 노드의 연결 노드 중 방문하지 않은 노드로
다음 노드의 값 = 현재 노드의 값 * 비율로 계산
DFS 실행하기 //재귀 함수
}
//노드 클래스 선언
c 노드 {
다음 노드, 비율 1, 비율 2
}
Code.
package numberTheory;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;
public class P1033_cocktail {
static boolean[] visited;
static long lcm;
static long mass[];
static ArrayList<cNode>[] A;
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
A = new ArrayList[N];
visited = new boolean[N];
mass = new long[N];
lcm = 1;
for (int i = 0; i < N; i++) {
A[i] = new ArrayList<cNode>();
}
for (int i = 0; i < N - 1; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
int p = sc.nextInt();
int q = sc.nextInt();
A[a].add(new cNode(b, p, q));
A[b].add(new cNode(a, q, p));
lcm *= (p * q / gcd(p, q));
}
mass[0] = lcm;
DFS(0);
long mgcd = mass[0];
for (int i = 0; i < N; i++) {
mgcd = gcd(mgcd, mass[i]);
}
for (int i = 0; i < N; i++) {
System.out.print(mass[i] / mgcd + " ");
}
}
private static long gcd(long a, long b) {
if (b == 0) {
return a;
} else {
return gcd(b, a % b);
}
}
public static void DFS(int Node) {
visited[Node] = true;
for (cNode i : A[Node]) {
int next = i.getB();
if (!visited[next]) {
mass[next] = mass[Node] * i.getQ() / i.getP();
DFS(next);
}
}
}
}
class cNode {
int b;
int p;
int q;
public cNode(int b, int p, int q) {
super();
this.b = b;
this.p = p;
this.q = q;
}
public int getB() {
return b;
}
public int getP() {
return p;
}
public int getQ() {
return q;
}
}
Leave a comment