문제https://www.acmicpc.net/problem/13335 풀이큐를 이용한 구현으로 문제를 해결했습니다. while문을 돌며 queue에 어떤 값을 집어 넣을지에 대한 조건을 정의합니다. 만약, 다음 차례의 트럭의 무게와 현재 다리에 있는 트럭 무게가 최대 허용 무게보다 작다면, queue에 다음 트럭을 넣고 아니라면 queue에 0을 넣어줍니다. 그리고 매번 큐의 사이즈를 체크하여 큐의 크기 다리 길이와 같으면 queue에서 poll해줍니다. 큐에 값을 add, poll 할 때에는 현재 다리의 트럭 무게를 업데이트해주었습니다. 아래는 소스코드입니다.소스코드import java.util.ArrayDeque;import java.util.Queue;import java.util.Scan..
Java/BOJ
문제https://www.acmicpc.net/problem/11728 풀이두 가지 방법으로 문제를 해결할 수 있었습니다. Arrays.sort 메서드를 통해 단순히 구현하는 법과 포인터를 이용하는 법입니다. 포인터를 이용할 때에는, 두 배열에 대해 0부터 시작하는 포인터를 하나씩 두고, 둘 중 하나라도 포인터가 끝에 도달하면 while문을 멈춥니다. 그리고 끝까지 도달한 배열이 아닌, 다른 배열의 값을 모두 append 해주었습니다. 아래는 소스 코드입니다.소스 코드1. pointer 이용import java.util.Arrays;import java.util.Scanner;public class Main { public static void main(String[] args) { ..
문제https://www.acmicpc.net/problem/2828 풀이 포인터를 이용해 문제를 해결했습니다. 바구니의 시작 점을 start, 그리고 끝 점은 end = start+M-1 로 표현할 수 있습니다. 그리고 들어오는 입력 값이 start와 end 사이에 있다면 이동하지 않아도 되고, 만약 범위 밖이라면 start와 end를 통채로 ++, --를 통해 옮겨주었습니다. 그리고 이동할 때마다 moveDist라는 변수를 ++ 해주며 답을 구했습니다. 아래는 소스 코드입니다.소스 코드import java.util.Scanner;public class B2828_사과담기게임 { public static void main(String[] args) { Scanner sc =..
문제https://www.acmicpc.net/problem/14244 풀이트리의 개념을 활용한 구현 문제입니다. 이 문제에서 리프란, 간선이 하나밖에 없는 노드입니다. 그래서 트리의 끝만 포함되는 것이 아니라, 조건이 맞다면 루트도 포함될 수 있습니다. 소스 코드의 주석으로 풀이를 대체하겠습니다. 소스 코드import java.util.Scanner;public class B14244_트리만들기 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int M = sc.nextInt(); int leafCount = 0..
문제https://www.acmicpc.net/problem/17073 풀이트리 문제입니다. 처음 아이디어는 트리를 순회해야한다는 생각에 트리를 dfs로 순회하며 리프 노드와 깊이를 구했습니다. 그래서 2의 (깊이) 승을 w에 나누어W/(Math.pow(2, depth));와 같이 식을 구성했습니다.그런데 생각해보니, 수학에서 결합 법칙을 생각해보면, 모든 확률의 합은 1이기 때문에 기대 값은 W 그대로라는 것을 알 수 있습니다. 그래서 결과는 W / 리프 노드의 개수를 구한 값입니다. ArrayList에 입력을 받을 때 양방향 간선 트리에서 리프노드의 연결 값의 size는 1이라는 쉬운 특징이 있었습니다. 이를 통해 리프노드의 개수를 세어주었습니다. 추가로, 이 문제에서 부모 노드가 자식 노드보다..
문제https://www.acmicpc.net/problem/14267 풀이트리에서의 dfs 방법으로 문제를 해결했습니다. dfs이지만, 배열에서의 누적 합의 매커니즘과 굉장히 비슷한 문제입니다. 누적합은 쉽게 말해, [0,1,1,0,1,1] 과 같은 배열을 nums[i+1] += nums[i] 와 같은 식을 통해 [0,1,2,2,3,4] 과 같은 결과를 도출하는 것입니다. 이 문제도 마찬가지로, 배열에 값을 입력받고 누적합을 돌리는데 위와 같이 인덱스가 연속된 경우가 아닙니다. 그래서 연속된 인덱스를 dfs로 탐색하며 누적합을 시키는 매커니즘입니다. 값을 입력받을 때, list에 사원 번호를 연결시킵니다. 그리고 1번(사장)에서 dfs를 시작해, score 배열을 누적 합을 시켜나갔습..
