본문 바로가기
반응형

전체 글

 (168)
[백준] 16234번 인구 이동 16234번 인구 이동 1. 이해하기 모든 나라의 크기는 1x1이고, 각 나라의 인구수는 맵에 나와있는 숫자이다. 각 나라에 인접한 나라 사이에는 국경선이 존재한다. 인구 이동이 시작되는 방법 국경선을 공유하는 두 나라의 인구 차이가 L이상, R 이하이면, 국경선을 하루동안 연다. 국경선이 모두 열렸다면, 인구 이동을 시작한다. 국경선이 열려있는 나라는 연합이라 부른다. 연합을 이룬 나라들의 인구수는 (연합의 인구수)/(연합을 이루고 있는 칸의 캐수)가 된다. 소수점은 버린다. 연합을 해체하고, 모든 국경선을 닫는다. 인구 이동이 몇 번 발생하는지 알아낸다. 시뮬레이션 문제이다. 2. 구현하기 인접한 국가와의 인구수 차이가 L 이상, R 이하인지 살펴보고 맞으면 연합으로 포함한다. bfs를 이용하여 구한..
[백준] 5373번 큐빙 5373번 큐빙 1. 이해하기 큐브를 돌려가면서 그때의 윗 면의 색상을 구하는 문제이다. 큐브를 돌렸을 때 돌린 면을 포함, 다른 면들이 어떻게 변하는지 구현하는 시뮬레이션 문제. 2. 구현하기 각 면에 대해 그 면을 시계 방향, 반시계 방향으로 돌렸을 때 어떻게 되는지 구현. 그림을 그려서 이해하면 이해하기 쉽다. void temp_to_cube(char temp[3][3], char cube[3][3]) { for(int i = 0; i < 3; i++) { for(int j = 0; j < 3; j++) { cube[i][j] = temp[i][j]; } } } void rotate_clock(char cube[3][3]) { char temp[3][3]; for(int i = 0; i < 3; i..
[백준] 15686번 치킨 배달 15686번 치킨 배달 1. 이해하기 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다. (r1,c1)과 (r2,c2) 사이의 거리는 |r1-r2|+|c1-c2|이다. 치킨집 중에서 최대 M개를 고르고, 나머지는 폐업시킨다고 할 때 도시의 치킨 거리가 가장 작게 되는 값을 구하는 문제. 모든 치킨집에 대해서 구해보는 완전탐색 문제. 2. 구현하기 각 집에 대해서 치킨 거리를 구한다. int get_chicken_distance(vector chicken, int x, int y) { int ret = get_distance(chicken[0].x,chicken[0].y,x,y); int size = chicken.size(); for(int i = ..
[백준] 15685번 드래곤 커브 15685번 드래곤 커브 1. 이해하기 드래곤 커브의 다음 세대가 변하는 규칙을 찾아야 한다. 규칙을 보면 가장 최근에 추가된 방향부터 차례대로 90도 반시계 방향 회전해서 다음 세대에 추가하는 것을 볼 수 있다. 규칙대로 드래곤 커브를 표시해주고 표시된 것 중 사각형의 갯수를 찾아서 출력해 주면 된다. 시뮬레이션 문제. 2. 구현하기 드래곤 커브의 다음 세대를 구해 반환해준다. vector get_next_cur(vector cur) { vector ret = cur; int size = cur.size(); for(int i = 0; i < size; i++) { int dir = cur.back(); cur.pop_back(); dir = (dir+1)%4; ret.push_back(dir); } ..
[백준] 15684번 사다리 조작 15684번 사다리 조작 1. 이해하기 사다리에 가로선을 놓아 길을 만들어 자신이 출발한 세로선과 끝난 세로선이 같도록 해야 한다. 사다리의 가로선을 모두 놓아보는 완전 탐색 문제. 2. 구현하기 사다리를 타고 내려가보면서 자신이 출발한 세로선에서 끝나는 경우인지 판단. bool is_all_match() { for(int i = 0; i = 0 and map[x][y-1] == num) { y--; } else if(y+1 < N and map[x][y+1] == num) { y++; } } x++; } if(y != i) return false..
[백준] 15683번 감시 15683번 감시 1. 이해하기 CCTV는 5가지 종류가 있다. 종류마다 감시할 수 있는 방법이 다르다. CCTV는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있지만 벽은 통과해서 감시하지 못한다. 이를 사각지대라 부른다. CCTV는 90도 방향으로 회전할 수 있다. CCTV의 방향을 적절히 정해서, 사각 지대의 최소 크기를 구해야 한다. 각 CCTV마다 방향을 달리해 사각지대를 구하는 완전탐색 문제. 2. 구현하기 카메라의 종류, 현재 위치와 가리키고 있는 방향을 받아와 그 방향으로 감시할 수 있는 영역을 표시한다. bool out_of_bound(int x, int y) { return x = N or y = M; } void mark_view_area(in..
[백준] 14891번 톱니바퀴 14891번 톱니바퀴 1. 이해하기 톱니바퀴가 서로 맞닿은 극에 따라서 옆에 있는 톱니바퀴를 회전시킬 수 있다. 옆에 있는 톱니바퀴를 회전시키는 경우는 맞닿은 극이 서로 다를 경우에 반대 방향으로 회전하게 된다. 톱니바퀴를 회전시킨 방법이 주어졌을 때, 최종 톱니바퀴의 상태를 구하는 문제. 시뮬레이션 문제. 2. 구현하기 톱니바퀴를 시계방향 혹은 반시계방향으로 회전시킨다. void rotate(int n, int dir) { if(dir == 1) { char temp = gear[n][7]; for(int i = 7; i > 0; i--) { gear[n][i] = gear[n][i-1]; } gear[n][0] = temp; } else if(dir == -1) { char temp = gear[n]..
[백준] 14890번 경사로 14890번 경사로 1. 이해하기 지도에서 지나갈 수 있는 길이 몇개인지 세는 문제이다. 지나갈 수 있는 길은 평평한 길이거나 경사로를 설치할 수 있는 길을 의미한다. 경사로는 높이 차이가 1인 곳, 경사로의 길이 만큼의 평평한 길이 있을 때만 설치할 수 있다. 경사로를 이미 설치한 곳에 또 설치를 할 수 없다. 시뮬레이션 문제. 2. 구현하기 행과 열의 특정 길이에 대해 경사로를 설치할 수 있는지 판단한다. 설치할 수 있으면 설치한다. bool can_install_row(int i, int st, int en) { int temp = map[i][st]; for(int j = st; j = N) { flag = false; break; } if(!can_install_col(i,st,en)) { fl..

티스토리툴바