본문 바로가기
반응형

분류 전체보기

 (168)
[백준] 14889번 스타트와 링크 14889번 스타트와 링크 1. 이해하기 전체 N명에서 N/2명으로 두 팀을 나눠서 각 팀의 선택된 사람들의 능력치 차이의 최소를 구하는 문제이다. 모든 경우를 다 해보는 완전탐색 문제. 2. 구현하기 N명에서 N/2을 고르는 방법을 만든다. 그 후 각 팀에서 고른 사람들의 능력치 차이의 최솟값을 반환한다. int solve(int index, int cnt) { if(index > N) return MAX; if(index == N and cnt == N/2) { int sum1 = 0, sum2 = 0; for(int i = 0; i < N; i++) { for(int j = 0; j < N; j++) { if(i == j) continue; if(selected[i] and selected[j]) ..
[백준] 14888번 연산자 끼워넣기 14888번 연산자 끼워넣기 1. 이해하기 수와 수 사이에 연산자를 하나씩 넣는데 주어진 수의 순서를 바꾸면 안 된다. 연산자는 수의 개수-1 개가 주어지기 때문에 모두 사용해야 한다. 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구해야 한다. 만들 수 있는 결과를 모두 만들어 보는 완전탐색 문제. 2. 구현하기 최대인 것과 최소인 것을 반환하기 위하여 구조체를 만든다. struct RET { int min_val,max_val; }; 연산자를 모두 쓰는데 오버해서 쓰면 최댓값과 최솟값을 반환해준다. RET solve(int index, int plus, int minus, int mul, int div, int val) { if(plus < 0 or minus < 0 or mul < 0 or d..
[백준] 14503번 로봇 청소기 14503번 로봇 청소기 1. 이해하기 맵의 끝부분은 모두 벽으로 되어 있다. 청소기는 바라보는 방향이 동, 서, 남, 북중 하나이다. 청소기는 다음과 같이 작동한다. 현재 위치를 청소한다. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 탐색을 진행한다. 왼쪽 방향에 아직 청소하지 않은 공간이 있다면, 그 방향으로 회전, 한칸을 전진하고 1번부터 진행한다. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다. 네 방향 모두 청소가 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진하고 2번으로 돌아간다. 네 방향 모두 청소가 되어있거나 벽이면서, 뒤쪽 방향이 벽이면 작동을 멈춘다. 로봇 청소기는 벽을 통과할 수 없다. 로봇 청소기가 청소한 영역의 크기를..
[백준] 14502번 연구소 14502번 연구소 1. 이해하기 연구소에 바이러스가 퍼지지 않도록 벽을 세워야 한다. 벽은 꼭 3개를 세워야 한다. 바이러스는 상하좌우로 인접한 빈 칸으로 퍼져나간다. 바이러스가 벽으로 인해서 퍼져나갈 수 없는 영역을 안전영역이라 한다. 안전 영역 크기의 최댓값을 구해야 한다. 2. 구현하기 바이러스는 상하좌우로 인접한 빈 칸으로 퍼져나간다. BFS를 이용하여 바이러스의 이동을 구현한다. void bfs(int r, int c) { queue q; q.push({r,c}); visited[r][c] = true; while(!q.empty()) { int x = q.front().x,y = q.front().y; q.pop(); for(int i = 0; i < 4; i++) { int nx = x+d..
[백준] 14501번 퇴사 14501번 퇴사 1. 이해하기 상담을 하여 가장 많이 받을 수 있는 금액을 얻는 방법. 모든 날의 상담을 할 수 있는 것이 아닌 최종 일전까지만 상담을 받을 수 있고 상담이 최종일까지 끝나야 한다. 완전탐색과 DP로 풀 수 있다. 2. 구현하기 완전탐색 방법 최종일을 넘는 경우에는 상담을 하지 못하므로 0을 반환한다. day+1을 넣어주는 경우는 그 날에는 상담을 하지 않고 다음 날에 상담을 하는 경우도 찾아주기 위해서이다. int solve(int day, int pay) { if(day > N) return 0; if(day == N) return pay; int ret = 0; ret = max(ret,solve(day+1,pay)); ret = max(ret,solve(day+schedule[d..
[백준] 14500번 테트로미노 14500번 테트로미노 1. 이해하기 가능한 테트로미노 5가지 모양을 종이 위에 놓아보며 테트로미노가 놓은 칸의 수들의 합의 최대를 구하는 문제. 테트로미노가 놓여질 수 있는 방법을 모두 구해서 값을 비교해보는 완전탐색 문제. 2. 구현하기 각 모양마다 나올 수 있는 방법을 모두 구해 합을 반환하는 함수 int get_max_sum(int x, int y) { int sum = 0; if(y+3 < M) { int temp = map[x][y]+map[x][y+1]+map[x][y+2]+map[x][y+3]; sum = max(sum,temp); } if(x+3 < N) { int temp = map[x][y]+map[x+1][y]+map[x+2][y]+map[x+3][y]; sum = max(sum,t..
[백준] 14499번 주사위 굴리기 14499번 주사위 굴리기 1. 이해하기 주사위는 지도 위에 윗 면이 1이고, 동쪽을 바라보는 방향이 3인 상태로 놓여져 있다. 가장 처음에 주사위에는 모든 면에 0이 적혀져 있다. 지도의 각 칸에는 정수가 하나씩 쓰여져 있다. 주사위를 굴렸을 때, 이동한 칸에 쓰여있는 수가 0이면, 주사위의 바닥면에 쓰여 있는 수가 칸에 복사된다. 주사위를 굴렸을 때, 이동한 칸에 쓰여있는 수가 0이 아니면 칸의 수가 주사위의 바닥면으로 복사되고 칸에 쓰여 있는 수는 0이 된다. 주사위를 지도의 바깥으로 이동시키는 명령은 무시하며 출력도 하지 않는다. 주사위가 이동할 때마다 주사위의 상단에 쓰여 있는 값을 출력하는 문제. 주사위를 직접 만들어 보거나 그려서 이해하는 시뮬레이션 문제. 2. 구현하기 주사위를 그려서 동쪽..
[백준] 13458번 시험 감독 13458번 시험 감독 이해하기 총감독관은 한 방에 오직 1명만 있어야 한다. 부감독관은 여러 명 있어도 된다. 각 시험장에 있는 응시생들을 모두 감시해야 할때 필요한 감독관 수의 최솟값 구하는 문제 구현하기 총감독관은 한명만 꼭 있어야 하므로 총감독관이 감시할 수 있는 인원수를 미리 빼놓는다. 남은 인원수를 바탕으로 부감독관이 감시할 수 있는 인원으로 나눈다. 이때 나머지가 있으면 부감독관 한명이 더 필요한 것이므로 한명을 더 더해준다. #include using namespace std; int a[1000000]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin >> n; for(int i = 0; ..

티스토리툴바