백준 문제풀이93 [백준][그리디] 1911 흙길 보수하기 c++구현 목차https://www.acmicpc.net/problem/1911문제 문제 아이디어좌표가 매우 크므로 좌표만큼 배열을 만드는 것은 무리다.따라서 계산해주어 O(N) 순회해야 한다. 웅덩이의 시작 포인트에서 널판지를 설치하면 최적해를 만족한다. 코드 구현#include #include #include#include#include #includeusing namespace std;typedef long long ll;ll N, L, a, b;int total = 0;vector> v;//반올림을 통해 항상 널판지로 채울 수 있게 하였다.ll gapMin(ll len, ll str) { double a = len; double b = L; ll gap = ceil(a / b); //.. 2024. 9. 20. [백준][백트래킹][브루트포스] 15683 감시 c++구현 목차 https://www.acmicpc.net/problem/15683문제 문제 구현 방향 CCTV의 최대 개수는 8개를 넘지 않는다. 이 부분이 핵심 포인트였다... 문제를 제대로 읽지 않고 완전 탐색 불가능한거 아니야? 하면서 그리디로 돌아갔다가 한참 헤맸다 ㅜ 문제는 꼼꼼히 읽어야 된다. 문제 아이디어그냥 백트래킹 잘 해주면 풀린다. 아이디어는 복구를 하기 위한 좌표를 저장해 놓고 저장해 놓은 좌표를 바탕으로 복구하면 된다. 코드 구현#include #include #include#include#include using namespace std;//cctv 구조체typedef struct CCTV { int num; int x; int y;}CCTV;//상 하 좌 우int dx.. 2024. 9. 19. [백준][누적합][구현] 27942 danceplant c++ 구현 목차https://www.acmicpc.net/problem/27942문제 문제 구현 방향누적합을 통해 하지 않으면 시간초과가 나는 문제이다. 탐색은 bfs와 유사하게 했지만 가장 큰 곳을 먼저 탐색하게끔 좌표를 따로 저장해 주었다. 코드 구현#include #include #include#include#include using namespace std;typedef struct Plant{ vector> v; int sum;}Plant;int N;int board[3001][3001] = { 0 };int searching[3001][3001] = { 0 };vector> v;//상하좌우int dx[4] = {0,0,-1, 1};int dy[4] = {-1, 1,0,0};Plant dire.. 2024. 9. 19. [백준][dp] 2565 전깃줄 c++ 구현 목차https://www.acmicpc.net/problem/2565문제 문제 구현 방향생각보다 아이디어가 잘 떠오르지 않는다. 나도 처음에는 막혀서 답을 보아버렸다..아이디어는 총 세개이다. 1. 오른쪽 기준으로 정렬하기 -> 경우를 더 줄어야 한다.2. 전깃줄을 교차하지 않기 위한 전깃줄의 최대 개수 구하기로 바꾸어 생각하기 -> 이렇게 생각하면 아래와 같은 문제로 변한다. 3. 증가하는 가장 긴 부분수열 구하기 참고https://be-senior-developer.tistory.com/23 [백준][dp] 11053 가장 긴 증가하는 부분 수열 c++ 구현목차 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, .. 2024. 9. 18. 이전 1 2 3 4 ··· 24 다음 728x90
