PS
-
BOJ 17182 - 우주 탐사선PS 2024. 8. 24. 00:32
https://www.acmicpc.net/problem/17182 플로이드워셜 + 완전탐색 백트래킹으로 풀었다. 재밌는 문제였다. 처음에는 문제를 보자마자 N도 작고 해서 아 이거 플로이드 워셜이구나 생각했다.그래서 각 정점에서 다른 정점으로 가는 최소값을 구하고, 이제 한 정점에서 다른 정점으로 가는 최솟값들을 더해주면 된다고 생각했다.(0에서 1,2,3 번으로 가는 최소값을 보고 가장 최소인 값으로 이동하고, 또 그점에서 다른 정점으로 가는 최솟값들을 보고... 이런식으로 일종의 그리디처럼)그런데 하면서 든 생각이 그리디처럼 어느 한 정점에서 다른 정점으로 가는 최솟값들을 모두 더한 값이 전체의 최소값은 아닐 수 있다는 생각이 들었다.그래서 아 완전탐색이구나 라는 생각이 들어 완전탐색으로 풀었다.그..
-
BOJ 17298 - 오큰수PS 2024. 8. 22. 17:22
https://www.acmicpc.net/problem/17298 예전에 풀었었고, 다시 풀어본 문제다.처음 문제를 보고, 집가는 지하철에서 계속 생각하고, 잠자기 전에 계속 생각하다가 다음날 풀었을때 기분이 너무 좋았었다. 그런데 오랜만에 풀어보니 잘 풀리지 않고 몇번 틀렸다.그래도 결국 다시 풀어냈다! 접근방식은 스택을 사용하여 스택의 top이 항상 새로나오는 수보다 큰 수를 유지하게 하는 거다.(스택에는 내림차순으로 수가 저장되는 거다. 지금 설명으로는 애매한데, 밑의 설명과 코드를 보면 더 잘 이해가 될거다.) 먼저 정답배열을 전부 -1로 채워준다.새로운 수와 스택의 top을 비교한다. 새로운 수가 스택의 top보다 작다면, 오큰수가 아닌 거니깐 스택에 추가하고 넘어간다. 이때 새로운 수의 인덱..
-
BOJ 2467 - 용액PS 2024. 8. 20. 19:19
https://www.acmicpc.net/problem/2467 투포인터로 풀었다. 처음문제를 봤을때는 이걸 어떻게 해야하나, preSum을 구해야하나, 값을 입력받을때마다 0번인덱스와 더한값 저장, 1번인덱스와 더한값저장 이렇게 해야하나,,, 고민했다.그런데 그러기에는 숫자가 너무 컸다. N이 일단 100,000까지니깐 이렇게 하면 무조건 시간복잡도가 초과되었다. 문제를 다시 읽어보니 특성값이 -1,000,000,000부터 1,000,000,000까지였고 정렬되서 주어진다고 했다.값도 너무 크고, 정렬이라는 단어가 있으니 여기서 이분탐색을 떠올렸다.그러면 이제 이분탐색을 어떻게 해야할까... 이분탐색은 보통 시작과 끝을 더하고 그걸 2로 나눈 중간값을 구해서 그 중간값과 특정값을 비교하고 이걸 기반으..
-
BOJ 2638 - 치즈PS 2024. 8. 17. 23:33
https://www.acmicpc.net/problem/2638재밌는 문제였다.처음에는 외부공기와 접촉한 부분만 녹는다는 조건을 제대로 안보고, 그냥 두면이상이 공기와 접촉하면 녹이는 식으로 해서 틀렸다.그리고나서 문제를 제대로 읽고, 외부공기와 접촉한 부분이 두면이상일 때 녹게하기 위해 어떻게 해야할지 고민을 좀 했다. 이중반복문 완전탐색으로 가다가 치즈나오는 부분이 생기면 그때부터 bfs나 dfs로 치즈인 부분들만 탐색하게 할까, 어떻게해야할까 등등...그러다가 외부공기만 먼저 오염(?)시키고 난 후에, (0,0 부터 시작해 dfs로 0인부분들만 찾아서 오염시킨다.) 외부와 접촉하는 부분이 두개이상인 부분을 큐에넣고 저장한다음, 큐안의 내용물들을 모두 녹이는 방법을 떠올려서 이렇게 풀었다! (큐에 ..
-
BOJ 2512 - 예산PS 2024. 8. 14. 21:41
https://www.acmicpc.net/problem/2512 2분 탐색으로 풀었다.오랜만에 2분탐색 문제를 풀어서 재밌었다.주의할 점은 출력을 '배정된 예산들 중 최댓값인 정수를 출력한다.' 는 것이다. 총 예산이 400이고, 지원요청이 100, 80, 95로 이 안에서 모든 예산을 지원할 수 있다고하자.이 때, 상한선을 130으로 해도 모두 지원가능한데, 어차피 최대 100만 지원하면 되므로 배정된 예산들 중 최대값인 정수는 100이 되고, 답은 100을 출력하면 된다. 만약 총예산이 더 적어서 상한을 90으로 해야한다면 90을 출력해야 한다. 오랜만에 2분탐색 문제를 풀어서 재밌었고, 문제를 읽자마자 2분탐색을 써야한다는 게 떠올라서 너무 좋았다.#include using namespace st..
-
BOJ 17142 - 연구소 3PS 2024. 8. 13. 17:10
https://www.acmicpc.net/problem/17142 재밌는 문제였다. 처음 입력받을 때 바이러스의 위치들을 따로 저장해둔다.그리고 조합을 구해 어떤 바이러스들을 활성화시킬지 경우의 수를 뽑는다.뽑힌 경우의 수를 돌며 바이러스를 퍼뜨리기 시작하는데, 이때 bfs를 사용했다.그런데 일반적인 bfs를 도는 게 아니라, 층을 나눠주는 게 필요하다. 왜냐하면 큐에 여러개가 들어있는데, 1초가 지났을때, 2초가 지났을 때 이런식으로 구별이 필요하기 때문이다.그래서 while문 안에서 qSize를 받고, qSize만큼의 반복문이 끝나면 시간이 올라가게끔 구별해줬다.이걸 무슨 기법이라고 했는데, 이름은 까먹었다. 파티션 뭐 이런거였던 거 같은데어쨌든 이렇게 해주면서 시간을 비교해 최소시간을 출력해주면 ..
-
BOJ 2631 - 줄세우기PS 2024. 8. 5. 12:14
https://www.acmicpc.net/problem/2631 문제를 보고 좀 생각하다가 LIS를 이용하면 된다는 걸 깨달았으나, LIS를 푼지 너무 오래되어 LIS를 구현하지 못해 실패했었다.LIS 알고리즘을 다시 보고와서 정답을 맞출수있었다. LIS 문제 몇개 풀어봐야겠다...#include using namespace std;int n;int a[204];int cnt[204];int main(){ cin >> n; for (int i = 0; i > a[i]; } fill(cnt, cnt + 204, 1); // 초ㅣ장 lis를 구하고 전체길이 - lis 해주면 될듯 int longgest = 0; for (int i = 0; i cnt[i]) ..
-
BOJ 4485 - 녹색 옷 입은 애가 젤다지?PS 2024. 8. 4. 20:28
https://www.acmicpc.net/problem/4485 다익스트라 문제였다. 그런데 이제 어떤 정점에서 다른정점까지의 비용이 1 4 8 이런식으로 주어지는 게 아니라,2차원 배열로 어떤 정점에 도착했을 때의 비용이 주어지는.그러니깐, 한곳에서 다른곳으로 이동가능한 간선이 주어지는 게 아니라 bfs나 dfs문제 풀때처럼 상하좌우로 움직이는 거 가능하고, 어디 도착하면 거기 비용이 플러스 되는 형식이다. 재밌었다.#include using namespace std;int n;int a[130][130];int num;int inf = 1e9;int d[130][130];int dirY[4] = {1, -1, 0, 0};int dirX[4] = {0, 0, 1, -1};int main(){ i..