목록알고리즘/BOJ (28)
대웅짱님의 블로그
문제: https://www.acmicpc.net/problem/14502 바이러스를 연구하던 연구소에서 바이러스가 유출됐다. 우리는 빈 공간에 벽을 세워 바이러스의 확산을 막을 수 있다. 벽은 반드시 3개를 세워야한다. 연구소 지도에 바이러스 위치와 벽, 빈 공간이 주어졌을 때 어느 곳에 벽을 세워야 바이러스위 확산을 최대한으로 막을 수 있냐고 묻는 문제이다. 지도의 크기는 최대 10*10 이므로 완전 탐색을 이용해 풀면 된다. 나는 벡터를 하나 만들어 빈 공간의 위치를 저장해두고 그 벡터의 아이템 중 3개를 골라 벽을 세우는 방식으로 코드를 작성했다. 벽을 세운 후 바이러스(2)를 찾아 dfs를 진행하고 남아있는 빈 공간의 개수의 합을 최대로 갱신해가면서 저장했다. 끝. 1234567891011121..
문제: https://www.acmicpc.net/problem/14501 이번 문제는 퇴사이다. 앞으로 퇴사할 날이 주어지고 퇴사 전까지의 일과 비용이 주어졌을 때 최대한 뽕 뽑고 퇴사할 경우 얼마를 벌 수 있냐고 묻는 문제이다. 딱 봐도 DP문제인 것 같아서 DP로 풀었다. 그 날 일을 선택하느냐 그냥 넘어가느냐 두 가지로 나누어 주고 최대 값을 구해주면 된다. 끝. 12345678910111213141516171819202122232425#include#include#includeusing namespace std;int dp[20], n;pair arr[20];int func(int num){ if(num > n) return -987654321; int &ret = dp[num]; if(ret ..
문제: https://www.acmicpc.net/problem/14500 이번 문제는 테트로미노이다. 주어진 다섯 가지 도형 중 딱 하나만을 사용해 종이에 올려 놓았을 때 가장 큰 값을 구하는 문제이다. 예전에 한 번 풀고 이번 기회에 다시 풀어서 풀이가 두 가지가 있다. 매우 비슷하지만 약간 차이가 있으니 둘 다 소개하겠다. 사실 똑같은 방법이긴 하다. 먼저 첫 번째 방법은 도형을 잘 살펴보면 알겠지만 T 모양의 도형을 제외하고 나머지 도형들은 한 붓그리기 처럼 처음 점에서 마지막 점 까지 쭉 연결할 수 있다. 이걸 이용해 상 하 좌 우 를 숫자로 세 자리 순열을 만든다. ex) 111 ~ 444 처음 점과 이 세 자리 순열을 이용해 도형을 만든다. 이때 주의해야할 점은 아래 -> 위, 왼 쪽 -> ..
문제: https://www.acmicpc.net/problem/14499 주사위 굴리기. 지도 위에서 주사위 굴리는 것을 시뮬레이션 하는 문제이다. 룰은 이렇다. 주사위를 동 서 남 북으로 굴릴 수 있으며 주사위는 처음에 여섯 면 모두 0이라는 숫자를 가지고 시작한다. 만약 굴린 주사위의 위치에 지도의 숫자가 0이 아니라면 숫자가 주사위 바닥 면에 스며들고 지도의 숫자는 0이된다. 굴린 주사위의 위치에 지도의 숫자가 0이라면 주사위의 바닥 면의 숫자가 지도위에 복사된다. 이렇게 주사위를 굴릴 때 마다 위에서 봤을 때 보이는 주사위의 숫자(상단 면)를 출력하는 문제이다. 만약 주사위를 굴릴 때 지도 밖으로 벗어나는 명령이 있을 경우에는 이 명령을 무시한다. 문제에서 요구하는 것은 그렇게 어렵지 않다. 이..
문제: https://www.acmicpc.net/problem/13458 이번 문제는 시험 감독문제이다. 각 시험장마다 응시자들이 있고 그 응시자들을 감독할 총감독관과 부감독관이 있다. 총감독관과 부감독관은 감시할 수 있는 응시자의 수가 정해져있다. 시험장마다 총감독은 한 명뿐이고 부감독관은 여려명 있을 수 있다. 시험장의 개수(N)와 각 시험장의 응시자 수(Ai) 그리고 총감독관(B)과 부감독관(C)의 감시 인원이 인풋으로 주어진다. 예제를 확인하면 알 수 있지만 예제 입력 4 복사5 10 9 10 9 10 7 20 예제 출력 4 복사10 이 예제에서 출력 값이 10 이라는 뜻은 총감독관 한 명은 무조건 시험장에 있어야 한다는 뜻이다. 부감독관의 감시 응시생 수가 20명이므로 각 시험장당 부감독관 한..
문제: https://www.acmicpc.net/problem/3190 오늘 문제는 뱀이다. 뱀이 이동하는 것을 시뮬레이션 할 수 있냐고 물어보는 문제이다. 문제의 조건은 다음 두 가지이다. 1. 뱀은 사과를 먹으면 몸 길이가 1 늘어난다. 2. 이동 중 자신의 몸이나 벽에 부딪히면 그때까지의 시간을 출력하면 된다. 3. 사과가 없으면 꼬리쪽이 줄어들어 몸 길이가 유지된다. 문제를 푸는 아이디어는 무척 쉽다. 그냥 구현하면 된다. 만약 코드 작성이 잘 안된다면 아래의 보기 중 문제가 있을 것 같다. 1. 방향 전환 2. 문제이해 3. 꼬리 먼저 이런 문제를 많이 안 풀어 봤으면 방향 전환을 어떻게 해야하나 어렵게 느껴질 수 있다 나는 배열을 이용해 방향 전환을 했다. 1234567891011 //상 우..
문제: https://www.acmicpc.net/problem/12100 2048 이라는 게임이 있다. 난 이 게임을 핸드폰 앱으로 처음 했었는데 상 하 좌 우 움직이면서 같은 숫자들을 합치면서 높은 수를 만들어 내는 게임이다. 이 문제 이름은 2048 (Easy) 이다. 주어진 정보를 이용해 2048 게임을 시뮬레이션 해보는 문제이다. Easy라는 단어가 들어간 이유는 아마 5번의 횟수제한 때문인 것같다. 친절하게 5번의 횟수를 정해준 이유는 완전탐색을 하라는 뜻으로 받아들이면 된다. 마침 보드의 최대도 20*20 밖에 안된다. 상 하 좌 우를 나타낼 1~4까지의 숫자를 5자리 순열로 만들고 (ex: 11111 11112 11113 .... 44443 44444) 각 순열의 이동이 모두 끝난 후의 보..
문제: https://www.acmicpc.net/problem/13460 오랜만에 구슬 탈출 문제를 풀어봤다. 몇 가지를 제외하고는 일반 bfs문제와 크게 다르지 않다. 1. 가져가는 주체가 빨간 구슬과 파란 구슬 두 개이다. 2. 한 번에 한 칸씩 움직이는 것이 아니라 갈 수 있는 곳 까지 움직인다. 3. 빨간 구슬만 목적지에 도착해야 한다. 이 것만 신경써주면 크게 어렵지 않은 문제이다. 다만 생각할게 많아서 귀찮을 뿐. 문제 푸는 원리는 이렇다. 큐에 빨간 구슬과 파란 구슬의 좌표를 가지고 간다. 무한 루프 방지를 위해 visit 배열을 사용하는데 여기도 마찬가지로 빨간 구슬과 파란 구슬의 좌표를 한번에 가진다. 그리고 각각 구슬을 서로 신경쓰지 않고 같은 방향으로 굴릴 수 있는 곳 까지 굴린다...