전체 글107 [sort] 백준 3079번 - 입국심사 N개의 입국심사대 M명의 입국자 시간대로 본다면 결국 분 대별로 각 심사대 라인에서 수용할 수 있는 인원이 정해진다 결국 시간이 늘어날 수록 심사완료할 수 있는 수가 늘어나는 정렬의 구조! -> 이분 탐색 최대의 시간 = 입국자가 10^9일 때 1개의 줄이 있는 경우 = 10^18 int 형은 10^9 -> long long 자료형 사용한다 #include #include #include #include using namespace std; #define endl '\n' #define DIV 1000000009 long long N, M; int gate[1000000]; int main() { ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0); cin>>.. 2021. 2. 13. [Sort] 백준 2805번 - 나무 자르기 H 초과하는 나무의 부분만 자른다 자른 나무들의 합 >= M 1. 내림차순으로 나무들을 Sort 2. 높이의 최대값이라는 것 = 최대한 잘린 나무들이 M에 가까워야 한다 3. 가장 큰 나무의 높이에서 M을 뺀 만큼 사이의 범위를 이분 탐색하여 잘린 나무들의 합이 M에 제일 가까운 수 H를 찾는다. 처음 코드 실패 -> 시간 초과 #include #include #include #include using namespace std; #define endl '\n' #define DIV 1000000009 int N, M; int tree[1000000]; bool compare(int a, int b){ return a>b; } int main() { ios_base::sync_with_stdio(0); c.. 2021. 2. 10. [DP] 백준 1757번 - 달려달려 DP를 안 쓴다면) 매분 달릴지 말지를 결정하는 완전 탐색을 진행해야 한다. 2^N이 되는데 N DP? DP를 쓴다면) 상태 3가지 존재 1. 몇분 2. 지침 지수 3. 달리는 상태 dis[n] -> 각 시간에서의 갈 수 있는 거리 dp[x][y][z] -> '최대한 갈 수 있는 거리'로 dp를 설정 x : 분 y : 지침 지수 z : 달리는 상태 (1:달림 0:쉼) M은 2라고 가정 지침지수 0인 경우 y=0) dp[x][y][0] = max( dp[x-1][y+1][0], dp[x-1][y+1][1], dp[x-1][y][0] ) 지침지수 1인 경우 y=1) dp[x][y][0] = max( dp[x-1][y+1][0], dp[x-1][y+1][1] ) y-1에서 값을 가져올 수 없는 이유 >> y-.. 2021. 2. 5. [DP] 백준 15988번 - 1, 2, 3 더하기 3 생각하기 20을 나타내는 방법의 수 = 4를 나타내는 방법의 수 x 16을 나타내는 방법의 수 각 숫자 나타내는 방법의 수 구하는 방법 = 백트레킹? 하짐나 DP로 풀어야 하는 문제이기 때문에 DP적으로 생각! dp[num] = dp[num-1] + dp[num-2] + dp[num-3] 마지막에 각 단계에서 부족했던 숫자들만 더해서 값을 뽑을 수 있다 1을 구하는 방법에서 2을 더하는 방법 2를 구하는 방법에서 1을 더하는 방법 이미 구해 놓은 값들을 통해 구해낸다 * 각 숫자 때마다 dp값을 도출하기 #include #include #include #include #include #include #include #include #include using namespace std; #define end.. 2021. 1. 28. 이전 1 ··· 21 22 23 24 25 26 27 다음