이분탐색으로 해결할 수 있는 문제다 mid일만큼 본다고 하면 mid/(g+b)만큼 g or b를 볼 수 있다 그럼 g*(mid/(g+b))만큼 좋은 날을 볼 수 있고 그 다음 볼수있는 날도 최대 g만큼 좋은날이다 결국 답은 g*(mid/(g+b))+min(mid/(g+b),g)로 나온다!! 근데 문제를 잘 보면 전체 도로를 어쨌든 공사는 해야하므로 최소 n일은 봐야한다 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 #include #include using namespace std; #define ll long long ll n, g, b; bool solve(ll mid) {..
DFS+ 그리디를 이용해서 풀 수 있다 우선 지나간 길은 지나갈 수 없으므로 길을 지나갈 때 마다 x로 바꿔주자 그리고 우리가 봐야할 방향은 위부터 봐야 아래 남아있는 정점에 대해 이득이다 따라서 위부터 아래로 시작점에서 dfs를 돌리며 끝까지 가는지 체크를 해보자! 문제의 핵심은 dfs를 조금 변형하는 부분에 있다고 생각한다 내가 만약 x행의 끝부분까지 간다면 true를 리턴해주면 된다! 아니라면 false~~! 결국 도착하는 사람들은 true를 통해 갈 수 있다고 답을 알려준다...! dfs 열공하자 소스코드 (C++) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 ..
그리디 문제다 정렬을 시키고 뒤에 화학물질부터 보면된다 냉장고의 (x,y)라고 할 때 y를 기준으로 잡고 다음 화학물질의 x가 현재 y를 넘는지 안넘는지로 판단할 수 있다 넘는다면 같은 냉장고안에 넣을 수 있다 그리고 y값은 더 뒤에있는 값으로 초기화해준다 그리고 범위를 안넘으면 냉장고를 늘려주면 된다! 자바는 pair가 없어서 구현해야한다..! 그리고 pq는 minheap이다!! JAVA 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 import java.ut..
이진트리로 주어진 사칙연산이 유효한지 출력하는 문제다 입력이 조금 복잡하게 들어오는거 빼고는 크게 어렵지는 않은 문제다! 문제의 조건을 생각해보면 내가 현재 노드가 숫자일 때, 연산자일 때 나눠보면 된다 1. 숫자일 때 => 자식을 가지고 있으면 무조건 false다 2. 연산자라면 => 내 자식 두명을 재귀타고가서 둘다 참이라면 true다 코드가 좀 헷갈릴 수 있지만 재귀적으로 생각하면 쉽게 풀 수 있다! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 import java.util.*; import java.io.*; public class So..