나의개발일지

https://www.acmicpc.net/problem/16953 A에서 B를 만드는 방법은 여러개이고, 현재 값에서 다음 값으로 갈때 어떤 연산을 해야 더 빠른지 알 수 없다.하지만 역순으로 생각하면 다르다! B에서 1이 있으면 무조건 1을 더하는 연산을 쓸 수 밖에 없으니 이 연산을 우선순위로 두고 나아가면 된다.즉, B -> A로 가면서 1이 있으면 1을 제외하고, 1이 없으면 2를 나누고, 두 연산 다 되지 않거나 B의 연산값이 A보다 작아지면 -1을 출력한다. package BOJ.Greedy;import java.util.Scanner;public class BOJ_16953_AtoB { public static void main(String[] args) { Scanner..

https://www.acmicpc.net/problem/19941 처음으로 그리디 문제 읽으면서 떠오른 생각왼쪽에 있는 버거부터 먹어야 사람이 먹을 수 있는 버거의 수가 최대가 된다.사람을 만났을 때 왼쪽부터 k만큼 탐색해서 버거가 있으면 먹고, 없으면 오른쪽 버거를 먹으면 된다.한번 먹은 버거는 또 먹을 수 없으니 check 배열로 먹은 버거는 체크해준다.  package BOJ.Greedy;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class BOJ_19941_햄버거분배 { static int n, k; ..

https://www.acmicpc.net/problem/1449  그리디는 항상 해결방법을 떠올리는 게 참 어려운 것 같다,,이 문제는 주어진 물이 새는 곳의 위치를 정렬 해 두고, 주어진 테이프 길이 안에 위치하는 지 확인하면 되는 문제이다.즉, 첫번째 위치에서 -0 .5를 시작지점(left)로 두고 + 테이프의 길이(l) 안에 다음 물이 새는 위치가 더 오른쪽에 위치한다면테이프의 개수를 1 카운트하고, 시작지점을 다음 물이 새는 위치 - 0.5 지점으로 변경해주면 된다.  package BOJ.Greedy;import java.util.Arrays;import java.util.Scanner;public class BOJ_1449_수리공항승 { public static void main(Str..

https://www.acmicpc.net/problem/2217 각 각의 로프의 최대 중량이 주어지고, n개의 로프를 병렬로 이용하면 물체 무게를 n빵해서 들어올릴 수 있다.주어진 예제로 생각해 보자면, 15 로프를 이용하면 최대 15까지 들 수 있지만 10 로프를 함께 이용하면 최소 중량인 10의 2배(로프가 2개니까)까지 들 수 있다.그럼 10과 15 로프를 병렬로 이용하는 게 최선이다.만약, 주어진 로프가 5와 20 이라면 20 로프 하나로 20을 들 수 있고, 5 로프를 함께 이용하면 5*2=10밖에 들지 못한다.따라서 20로프를 하나만 이용하는 게 최선이다.이를 통해, 우선 병렬보다는 최대 중량의 로프 1개를 이용할 때를 확인해보는 게 우선순위라는 것을 알 수 있고, 그 뒤로는 n빵일 때를 차..

https://www.acmicpc.net/problem/1789 https://www.acmicpc.net/problem/2457 문제 부분집합으로 풀다가 시간초과 나서 보니 그리디,,,어려워 그리디,, 이번주는 그리디 뿌셔야겠다싶어서 시작으로 고른 문제N의 최댓값을 고르기 위해서는 1부터 1+2+3+4+5+... 더해가다가 S를 딱 넘은 시점에 숫자 하나만 빼주면 된다.즉, S가 11 이라고 했을 때, 1+2+3+4+5 일 때 4를 빼주면 됨!package BOJ;import java.util.Scanner;public class BOJ_1789 { public static void main(String[] args) { Scanner sc = new Scanner(System.in..

https://www.acmicpc.net/problem/2644 오늘은 작년에 풀었던 문제였다전형적인 DFS 문제로 시작노드에서부터 목표노드 까지의 거리를 구하면 된다!방문 순서가 아닌 노드 사이의 거리이므로 dfs 함수에 재귀로 같이 cnt를 돌려야 한다.** 도착하지 못하는 경우 -1 출력이므로, ans는 -1로 초기화 해주기!! package STUDY;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.List;import java.util.StringTokenizer;public class Day08_BOJ_..