본문 바로가기

백준 문제 풀이

 (148)
백준 16235 나무 재테크(C++) https://www.acmicpc.net/problem/16235 구현 자체도 정신을 똑바로 차려야하고 0.3초라는 매우 적은 시간 제한으로 인해 최적화를 잘 해줘야했다. 각 땅의 상황을 계절에 맞게 조절하는 것이 관건인 문제였다. 그리고 한 타일에 나무가 여러그루를 잘 컨트롤해줘야 했다. 나의 경우 2차원 자료구조를 사용하기 싫어서 1차원으로 사용후 x, y 좌표를 변화해주는 작업을 했는데 지금 생각하니 굳이 필요없는 작업인 것 같다. 이 문제에서 핵심은 N  조건에서 여러 나무가 있다면 나이가 가장 어린 순서대로 처리해주어야하기 때문에 처음엔 우선순위 큐를 사용했다. 예제는 모두 통과했지만 43퍼센트에서 시간초과가 발생했다. 그리고 질문게시판과 구글링을 통해 우선순위큐가 아닌 덱이 답이라는 것을 알..
백준 32176번 - 통신 시스템의 성능 저하(C++) https://www.acmicpc.net/problem/32176첫 풀이론 bfs를 통해 가장 가까운 K 개를 찾으려 했다. 경로 손실은 적을수록 좋기 때문이다. 그러나, 결국 이 방식도 K1 개의 모든 경우를 조합해보는 것과 다를바가 없다.그래서 이 문제는 최적화된 브루트포스가 정답이다.문제 조건을 봤을 때, Ex) N = 4, M = 14이면, K1 = 10, 11, 12, 13, 14 중 하나가 된다. 그리고 가능한 경우의 수는 14 combination 10, 14 combination 11, 14 combination 12, 14 combination 13, 14 combination 14 조합의 성질에 따라 14 combination 4, 14 combination 3, 14 combinat..
백준 6588번 - 골드바흐 추측 (C++) https://www.acmicpc.net/problem/6588 에라토스테네스의 체를 이용해 소수르 판별하고, 이후 완전탐색을 진행했는데 시간초과가 났다. 그래서 두번돌면 안되는 것을 확인했고,  i, n - i 가 둘 다 소수인 것을 찾아야한 다는 것을 생각해내었다. #include #include #define MAX 1000000using namespace std;vector primeNum;bool* check = new bool[MAX];int main(){ cin.tie(NULL); ios_base::sync_with_stdio(0); for(int i = 0; i > tmp; while(tmp != 0){ bool flag = false; ..
백준 25214번 - 크림 파스타(C++) https://www.acmicpc.net/problem/25214최솟값을 저장해두고, 현재 들어오는 값에서 뺀 값과, 이전 정답 값을 비교해가며 정답을 출력하면 되는 문제이다. 아이디어를 떠올리는 것이 생각보다 어려웠던 문제#include #include using namespace std;int dp[200001];int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int N; cin >> N; int minValue = 1000000001; int maxValue = 0; for(int i = 0; i > value; maxValue = max(maxValue, value); minV..
백준 5911번 - 선물 (C++) https://www.acmicpc.net/problem/5911 이 문제는 N이 1000이고 딱 하나의 물건만 할인할 수 있기 때문에 브루트포스 방식으로 모든 선물을 할인해볼 수 있다. 그래서 N * N으로 해결할 수 있다. 먼저 모든 선물을 하나씩 할인해보고 그 이후 비용이 덜 드는 순서대로 정렬하고 가능할 때 까지 선물을 보내보면 된다. 그리고 만약 여기서 할인할 수 있는 선물이 여러개가 된다면 https://www.acmicpc.net/problem/25947 이 문제가 된다. 할인할 수 있는 선물이 한개가 아니기 때문에 N * N 으로풀 수 없는 여러개의 조합이 되어버려 브루트포스는 사용할 수 없고 이 문제에선 먼저 정렬을 통해 오름차로 만들고 이후 막혔을 때 할인을 계속 해보면서 정답을 찾아간..
백준 13904번 - 과제 (C++ / Greedy 알고리즘) https://www.acmicpc.net/problem/13904 문제를 접했을 때, 남은 일수를 먼저 할 것인가, 가장 많이 점수를 주는 과제를 수행할 것인지 잘 생각해야하는 문제이다. 가장 많은 점수를 주는 과제는 반드시 처리되어야 하지만, 최대한 나중에 밀어두고 처리해야한다. 왜냐하면  10 10005 1001 999 이라하자, 그렇다면 가장 많이 주는 과제는 10일이나 남았지만 먼저 처리해버리면 999를 주는 과제를 처리할 수 없다. 그러므로  TASK[DAYS] = DAY 일에 처리할 과제의 점수 가 들어있도록 하는 구현 방법을 사용해야한다. 이것을 떠올리기가 쉽지 않아 난이도가 있다. 보통 그리디 문제라하면 어떤 answer를 갱신하는 식으로 처리하기 때문이다. 그래서 그리디와 자주 함꼐하는..
백준 1990번 - 소수인팰린드롬 ( C++ / 에라토스테네스의 체) https://www.acmicpc.net/problem/1990 에라토스테네스의 체를 사용하면 간편하게 풀리는 문제...... 라고생각했으나 계속 시간초과가 나서 당황했다. 에라토스테네스의 체를 사용하는 방법은 두가지가 있다. 1. 범위 내의 소수 모두 찾아내기 int main(){bool check[10000]; for(int i = 2; i * i  2. 소수 판정하기bool Eratos(int N){ if(N  소수 판정 또한 O(sqrt(N)) 으로 판단해낼 수 있다. 그렇다면 이 문제는 b가 1억까지 있기 때문에 결국 1억 * 소수 판정이 들어가서 무조건 시간초과인데 어떻게 해야할까 생각이 들었는데, 소수인 팰린드롬은 천만 이후 나오지 않는다고 한다..!!! 그래서 천만까지만 보면..
백준 1106 호텔 (C++) https://www.acmicpc.net/problem/1106Cost, Value가 정해져 있는 다이나믹 프로그래밍 배낭문제이다.다만 이 문제는 평범한 배낭문제와 달리 중복을 허용한다. 그래서 이 문제는 일반적인 배낭 문제의 변형이다. 일반적인 식은 다음과 같다.for(int i = 1; i = cost){ dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cost] + value); } else{ dp[i][j] = dp[i - 1][j]; } } } i번의 행을 만들 때는 i - 1번 행을 보고 표를 갱신하게 된다. 그래서 i - 1행에는 당연히 이번 아이템이 ..

티스토리툴바