본문 바로가기

백준 문제풀이124

[백준][백트래킹][브루트포스] 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.
[백준][스위핑] 1931 회의실 배정 c++구현 목차https://www.acmicpc.net/problem/1931문제 문제 접근 방향생각보다 아이디어가 잘 떠오르지 않았다. 하지만 N이 100000이라는 것을 보아 O(N) 시간으로 탐색해야 한다는 것을유추할 수 있다. 또한 경우를 줄이기 위해 정렬을 해야 한다는 것 또한 유추할 수 있다. 다음과 같이 3가지 정렬 기준이 나올 수 있다. 1. 시작점 기준으로 정렬하기바로 반례가 나온다. 경우에서 제외시켜 준다. 2. 사이 크기로 정렬하기이것 또한 반례가 바로 나온다. 3. 끝점 기준으로 정렬하기이것은 반례가 안보인다. 한번 시도해볼 가치가 충분하다.  코드 구현#include #include #include#include#include using namespace std;typedef long lo.. 2024. 9. 15.
728x90

티스토리툴바