kimtetris 님의 블로그

[BOJ] 백준 1655 가운데를 말해요 c++ (우선순위 )

문제 https://www.acmicpc.net/problem/1655 풀이우선순위 큐를 하나만 사용해서 풀려다 시간초과가 나 다른 블로그를 참고했습니다https://velog.io/@rhkswls98/%EB%B0%B1%EC%A4%80-1655-C-%EA%B0%80%EC%9A%B4%EB%8D%B0%EB%A5%BC-%EB%A7%90%ED%95%B4%EC%9A%94 풀이 과정은 우선순위 큐를 2개로 분할해서 사용한다는 아이디어만 있다면 생각보다 간단했습니다. 1. 최대 큐와 최소 큐의 크기가 같다면 무조건 최대 큐에 값을 넣습니다. 2. 최대 큐 크기가 더 크다면 최소 큐에 값을 넣습니다. 3. 값을 삽입 후 각 큐의 top값을 확인했을 때 최대 큐가 크다면 값을 교환합니다. 3번의 경우 문..

문제https://www.acmicpc.net/problem/20055 풀이과정 1번은 트레일러와 로봇들의 위치를 구분해서 구현했습니다. "내리는 위치"는 도착하자마자 무조건 내리고, 1번 칸의 경우엔 새로 올라오기 때문에 0으로 만들어줬습니다. int tmp = dq.back();dq.pop_back();dq.push_front(tmp);for (int i = n - 1; i > 0; i--){ robot[i] = robot[i - 1];}robot[0] = 0, robot[n - 1] = 0; 과정 2번은 "내리는 위치" 이전 칸부터 뒤에서 앞으로 검사해나가며 조건에 맞는 경우에 로봇들이 한칸씩 움직이는 것을 구현했습니다. 그리고 움직인 경우엔 컨테이너의 내구도를 검사해줬습니다. for (..

문제 https://www.acmicpc.net/problem/1202 풀이먼저 보석들을 저장한 배열과 가방의 크기를 저장한 배열을 작은 값부터 오름차순으로 정렬해 줍니다. 그리고 정답을 저장할 변수는 long long으로 하지 않으면 int의 범위를 넘어 틀립니다. 작은 수 부터 구하는 이유는 priority_queue를 사용해서 현재 가방에 넣을 수 있는 보석 중 가장 가치가 높은 것을 구하기 위해서입니다. pair info[300001];int bag[300001];priority_queue pq;long long ans;...sort(info, info + n);sort(bag, bag + k);... 다음으로 가방을 기준으로 탐색을 시작합니다. 가장 작은 가방을 선택하고, 그 가방에 들어갈..

문제https://www.acmicpc.net/problem/1865 풀이벨만-포드 알고리즘의 경우 주로 그래프 이론에서 음수인 가중치가 있을 때 사용하는 알고리즘입니다. 그래서 문제를 읽자마자 벨만-포드 알고리즘을 써야 된다는 것을 알았습니다. 사용 배열은 모든 간선을 한 번에 돌기 때문에 1차원 벡터를 선언해주고, 현재까지 값을 저장할 배열을 선언했습니다. 일반 길의 경우엔 방향이 없어 양쪽을 모두 넣어주고, 워프는 단방향이기에 가중치를 음수로하여 저장했습니다. vector, int>> v;int dis[501];...v.push_back({{s, e}, t});v.push_back({{e, s}, t});......v.push_back({{s, e}, -t});... 어떤 간선에서 시작해도 결..

문제https://www.acmicpc.net/problem/16236 풀이먼저 이동할 상어의 위치를 저장할 shark, bfs에 사용할 visit과 상어의 크기, 먹이를 먹은 횟수를 저장할 변수를 선언했습니다. int sea[21][21], visit[21][21];vector> shark;int dx[4] = {0, -1, 1, 0};int dy[4] = {-1, 0, 0, 1};int ans = 0, size_shark = 2, cnt = 0; 다음으로는 큰 사이클입니다. 상어가 한 번의 먹이를 먹는 것을 하나의 사이클로 잡아 구현했습니다. 여기에 사이클을 진행하면서 먹이를 먹는 것과, 몸집을 불리는 것을 추가했습니다. 그리고 memset을 이용해 방문 여부를 계속 초기화해 줬습니다. whil..

문제 https://www.acmicpc.net/problem/16235 풀이deque를 사용하여 심어져 있는 나무들을 저장했습니다. int food[10][10];int ground[10][10];deque tree[10][10];int dx[8] = {0, 1, 1, 1, 0, -1, -1, -1};int dy[8] = {1, 1, 0, -1, -1, -1, 0, 1}; 칸마다 다르게 작동하기 때문에 봄과 여름을 한 번에 처리했습니다. 봄은 단순히 땅에 남아있는 영양분과 나무의 나이를 비교하여 자랄 수 없는 경우엔 cnt로 개수를 저장했습니다. 그런 후 여름은 나무들이 나이순으로 저장되어 있기 때문에 뒤에서부터 cnt값만큼의 나무들을 양분으로 바꿨습니다. int cnt = 0;for (int l..

문제https://www.acmicpc.net/problem/15685 풀이가장 먼저 입력에 있는 인덱스 별 이동 방향을 잡아줬습니다. 처음에 dy를 {0, 1, 0, -1}로 했다가 한참 헤매버렸습니다.int flat[101][101];int dx[4] = {1, 0, -1, 0};int dy[4] = {0, -1, 0, 1}; 다음으로는 점을 그리는 함수를 만들었습니다. vector를 선언해서 세대별로 지나친 방향들을 저장했습니다. 1세대의 경우 0세대 까지 이동한 선을 90도 돌리고, 2세대의 경우 0, 1세대에 이동한 선을 90도 돌리고, 3세대의 경우 0, 1, 2세대에 이동한 선을 90도 돌리는 방식이기 때문에 쭉 기록하는 방식으로 구현했습니다. 0 -> 10 1 -> 2 10 1 2 1..

문제https://www.acmicpc.net/problem/15684 풀이문제 조건에 사다리를 최대 3개만 설치 가능하다는 것을 보고 바로 백트래킹으로 구현했습니다. 백트래킹의 진행 조건으로 사용한 것은 3개를 초과하는가? 현재 저장된 정보보다 값이 적은가? 조건에 맞도록 구현이 되었는가? 총 3가지입니다. 3개를 초과하는 경우엔 의미가 사라지고, 이미 저장된 답보다 커지면 불필요한 계산, 조건에 맞지 않으면 성립 자체가 되지 않기에 탈출 조건으로 지정해 줬습니다. void dfs(int n, int h, int cnt, int y){ if (cnt >= ans) return; if (check(n, h)) { ans = cnt; return;..

문제https://www.acmicpc.net/problem/10986 풀이먼저 구간의 총합에 대한 나머지 개수를 저장합니다. 이때 나머지 개수로 저장하는 이유는 구간을 정하는 상황에서 같은 나머지를 갖는 구간끼리 선택하면 M으로 딱 나눠 떨어지기 때문입니다. 예를 들어 1 3 2 5 2 8 2가 주어지고 3으로 나누는 상황이라는 가정하에 구간별 총합은 1 4 6 11 13 21 23이고 나머지는 1 1 0 2 1 0 2 입니다. 그러면 나머지 리스트에는 2 3 2가 저장됩니다. 이때 나머지를 저장하는 리스트의 크기는 int로 하면 차원이 축소되어 배열 크기 초과가 일어날 수 있기에 주의해줘야 합니다. long long mod[1001];...for (int i = 0; i > tmp; sum..

문제https://www.acmicpc.net/problem/15683 풀이문제를 접하자마자 cctv의 개수가 8개 이하라는 것을 보고 백트래킹을 통해 해결해야겠다는 아이디어를 생각했습니다. 다음으로는 x, y 이동 뱡향을 시계 방향으로 잡아주고, cctv번호에 맞는 감시 방향을 vector를 통해 미리 선언해 줬습니다. int room[8][8];int dx[4] = {0, 1, 0, -1};int dy[4] = {1, 0, -1, 0};vector dir[6] = {{}, {0}, {0, 2}, {0, 3}, {0, 2, 3}, {0, 1, 2, 3}}; 다음 단계로 앞서 생각해 뒀던 백트래킹을 사용하여 단계를 진행했고, 해당 단계에서 cctv가 회전하는 것을 반영하기 위해 "(i + dir[n..