본문 바로가기

백준 문제 풀이

 (152)
백준 3078번 - 좋은 친구(C++) https://www.acmicpc.net/problem/3078 상근이네 반의 N명 학생들의 이름이 성적순으로 주어졌을 때, 좋은 친구가 몇 쌍이나 있는지 구하는 프로그램을 작성하시오. 좋은 친구는 등수의 차이가 K보다 작거나 같으면서 이름의 길이가 같은 친구이다. 단순하게 생각하면 O(N * K)로 해결할 수 있지만 최적화를 통해 O(N)으로 통과시켜야하는 문제이다. AAABBBCCDDDE 예제를 가정하고 K = 2라 하자.큐의 길이가 K + 1 될 때 까지 큐에 이름의 길이를 넣고 맵에 개수를 저장한다.  큐 : AAA BBB CC맵: [3] = 2, [2] = 1 큐가 K + 1만큼 차면 큐에서 하나를 꺼내 꺼낸 이름의 개수가 몇개 있는지 확인하고 답을 갱신한다. 모두 친구가 될 수있는 범위만 모..
백준 8901번 - 화학 제품 (Java) https://www.acmicpc.net/problem/8901 AB, BC, CA를 만들 수 있는 모든 경우의 수를 확인해봐야하기 때문에 이 문제는 완전탐색 문제로 분류된다.AB를 0개 만들었을 때, BC를 0개 만들었을 때 -> CA가 만들어지는 개수가 정해진다.그러므로 AB를 가능한 만큼 만들어보고 각 경우의 수를 만들어보면 된다. A = 4B = 3C = 5 가 있다고 가정하자.  AB 는 B가 3이므로 3개까지 만들 수 있다.AB의 개수가 0이면 BC는 3개를 만들 수 있다. B를 사용하지 않았기 때문이다. BC를 0개 만들었다면 CA는 4개BC를 1개 만들었다면 CA는 3개BC를 2개 만들었다면 CA는 2개BC를 3개 만들었다면 CA는 1개 만들어낼 수 있다.  그리고 AB를 만들어낼 수 있..
백준 2651번 - 자동차경주대회 (Java) https://www.acmicpc.net/problem/2651 그리디로 풀자니 이전의 값을 계속 다시 사용해야한다.완전탐색을하면 2^100 승으로 당연히 시간초과다. 그래서 이 문제는 다이나믹 프로그래밍을 사용해야한다. DP 문제들은 다 그렇지만 1차원으로 해결가능한지? DP배열에 무슨 값을 넣어야하는지? 가 중요하다. 그리고 DP값에는 거의 모든 문제에서 정답이 들어간다는 것을 다시 한 번 명심하자. 즉,  DP[N] = N 지점까지 최소 정비로 올 수 있는 경우가 된다. 정비를 받지 않고 한번에 오는 것이 당연히 시간적으로는 손해가 안난다. 4지점의 경우, 1,2,3 에서 4까지 올 수 있다. 그리고 1,2,3에서 4까지 올수 있는 경우의 수는 다음과 같다. 1. 정비를 받고 올 수 있음2. 올 ..
백준 2212번 - 센서(C++) https://www.acmicpc.net/problem/2212이분탐색인가? 라는 생각이 들 수밖에 없는 문제였다. https://www.acmicpc.net/problem/1477 문제가 떠오르는 문제이기 때문이다. 1477번과 비슷하기도 하다. 만약 2212의 한 커버 거리의 최대나 최소를 구하라고 했다면 1477번 처럼 풀 수 있을 것이다. 이 문제는 시뮬레이션처럼 어디에 기지국을 설치할지 정하는 것이 아니라 각 센서 사이의 거리를 구해놓고 가장 먼 사이에다가 설치하면 되기 때문에 전체 값에서 그 값들을 빼주면 되는 문제였다. 정렬이던 그리디던 간에 아이디어를 떠올리지 못하면 매우 어려운 문제다. #include #include #include using namespace std;int main(..
백준 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..

티스토리툴바