본문 바로가기

cpp46

[개쉬운 풀이] 백준 19941 햄버거 분배 CPP (17일차) https://www.acmicpc.net/problem/19941문제생각1. 현재 학생들이 먹을 수 있는 햄버거를 그리디 형식으로 해결했다.2. 같은 방향으로 먹으면 최대치로 먹을 수 있다.풀이 #include #include using namespace std;const int MAX = 20001;int N, K;vector v;void input(){ cin >> N >> K; v = vector(N); for(int i = 0; i > v[i]; }}void print(){ for(int i = 0; i = N) continue; if(v[p] == 'H'){ v[p] = '.'; answer++.. 2024. 12. 8.
[개쉬운 풀이] 백준 16918 봄버맨 CPP (16일차) 문제 생각1. 처음에는 3초마다 행동이 진행되는 줄 알았다.2. 그러나 2초간격으로 생각하는 것이 맞다.3. 봄버맨은 2초에 한번씩 폭탄을 배치하고4. 폭탄은 3초에 한번씩 터진다.5. 따라서 매 time이 증가할때마다 폭탄이 터지는지 안터지는지 확인하면서,  2초에 한번씩 설치하면 된다. 풀이#include #include #include using namespace std;const int MAX = 201;int R, C, N;int map[MAX][MAX];int dx[4] = {1,-1,0,0};int dy[4] = {0,0,1,-1};void input(){ cin >> R >> C >> N; for(int i = 0; i > c; if(c == 'O') { .. 2024. 12. 7.
[개쉬운 풀이] 백준 1725 히스토그램 CPP (15일차) 문제 생각Stack 방식으로 다음 오는 막대 그래프를 저장하면 된다.Stack에는 오름차순으로만 저장이 된다. 왜냐하면 현재 최대 높이가 5 일때 그보다 작은 것이 오면 높이 5에 해당하는 사각형 넓이를 한번만 비교하면 되기 때문이다. 이때 5에 해당하는 크기를 비교하고 삭제하는 것이 아닌 높이 5는 그 밑 숫자들이 사각형을 이룰 때 사용이 될 수 있으므로, Stack에서는 제외될 수 있어도 카운팅을 통해 저장한다. 1. Stack에 현재 높이와 그 높이에 해당하는 사각형 갯수들을 저장한다.2. 최고 높이보다 큰 사각형이 오면 Stack에 저장한다.3. Stack에 담긴 막대들은 오름차순으로 되어있기 때문에, 뒤에 있는 작은 막대들은 앞의 큰 막대들 갯수에 영향을 받는다. 풀이#include #inclu.. 2024. 12. 6.
[개쉬운 풀이] 백준 2169 로봇 조종하기 CPP (14일차) 문제 생각1. 처음에는 단순하게 BFS로 풀면 된다고 생각했다. 그러나 각 배열에서 들어온 방향에 따라 결과가 달라질 수 있다는 것을 포착했다.2. 따라서 2중 배열이 아닌 3중 배열을 통해 방향성을 고려하였다.3. queue를 이용하다 보니 시간초과가 발생하였다. 따라서 이를 dfs와 dp를 활용한 수식으로 바꾸어 주었다. 풀이#include #include #include using namespace std;const int MAX = 1001;const int INF = -1e9;int N, M;int map[MAX][MAX];int dx[3] = {0,0,1}; //좌 우 밑int dy[3] = {-1,1,0};bool isVisited[MAX][MAX];int dp[MAX][MAX][3];voi.. 2024. 12. 5.

티스토리툴바