본문 바로가기

백준31

boj 17140 - 이차원배열과 연산(구현, 정렬) https://www.acmicpc.net/problem/17140 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net - 행, 열의 길이를 기록하면서 행>= 열 이면 R연산, 행 < 열 이면 C연산을 하면 된다 - 연산시 숫자-숫자출현횟수를 cnt배열에 기록하고(숫자 범위가 컸으면 해쉬로 저장했을듯), cnt배열을 다시 읽어내려가면서 우선순위큐에 {-횟수, -숫자} 로 넣어 정렬한다. C++는 priority_queue 최대힙이 기본이니까 최소힙으로 만들기 위해 -를 붙였고, 다시 top을 꺼내서 배.. 2021. 7. 8.
[BOJ]10026 - 적록색약(dfs) https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net - 쉬운 문제라 정리 안하려다가 타 블로그 해설을 보면 너무 어렵게 푸는 거 같아서 올려둠 - 모든 칸에서 dfs를 하면서 구간을 카운트하면 되고 적록색약인 케이스는 입력받은 맵을 수정해서(R -> G) 다시 dfs를 돌면 너무나도 쉽게 풀린다 #include #include #include #include using namespace std; const int dx[4] = {1, 0, .. 2021. 7. 3.
[BOJ] 6087 - 레이저 통신(BFS) https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net - 빛이 이동하면서 꺾이는 횟수를 저장하면서 BFS 탐색을 해도 될 것이고, 아래 코드처럼 선분 갯수를 카운트해서 1을 빼주면 거울 갯수가 된다. - 상하좌우로 빛이 이동하는 구간을 while문으로 표현할 수 있다는 점이 일반적인 bfs문제들과는 달라서 기록해둔다. bfs 탐색시 예외케이스를 continue문으로 빼버리는 템플릿에 익숙해지다보니 좀 햇깔렸다. - 지도의 크기를 W*H로 표.. 2021. 7. 2.
[boj]16236 - 아기상어(BFS, 우선순위 큐) https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net - 조건에 먹이를 먹는 조건의 우선순위가 정해져있다. (1. 아기상어 위치에서 가까운 순 2. 가장 위 3. 가장 왼쪽). 이를 other.x; } return d > other.d; } }; int n, size = 2, exp = 0, ans = 0; int a[20][20]; int check[20][20]; priority_queue pq; void bfs() { while (!pq.. 2021. 7. 2.

티스토리툴바