대웅짱님의 블로그
문제: https://www.acmicpc.net/problem/14891 4개의 톱니바퀴와 각 톱니바퀴의 8 개의 볼록 부분의 상태가 주어진다. 그 후 쿼리가 최대 100번 까지 들어오면서 톱니바퀴의 번호와 회전 방향이 주어졌을 때 쿼리를 모두 수행한 후 톱니바퀴의 상태를 묻는 문제이다. 문제의 주제는 시뮬레이션이다. 각 쿼리 수행 후 톱니바퀴의 상태를 틀리지 않고 잘 가지고 갈 수 있으면 어렵지 않다. 문제 해결 아이디어는 쿼리가 들어왔을 때 먼저 해당 번호의 톱니바퀴를 방향에 맞게 회전 한다. 그 후 해당 번호부터 오른쪽의 톱니바퀴를 전부 회전 시켜주고 끝나면 나머지 왼쪽의 톱니바퀴를 회전하면 된다. 톱니바퀴를 회전할 때 만약 극이 같아 회전하지 않았다면 그 쪽 방향은 더 이상 진행하지 않아도 된다..
문제: https://www.acmicpc.net/problem/14890 지도가 주어졌을 때 행이나 열로 이루어진 길 중 지나갈 수 있는 길은 모두 몇 개인지 묻는 문제이다. 우리는 경사진 곳에 길이가 L인 경사로를 설치해 길을 지나갈 수 있도록 만들 수 있다. 경사로 설치에는 조건이 필요하다. 1. 경사로는 높이가 1 이기 때문에 높이가 2 이상인 곳은 경사로를 설치할 수 없다. 2. 길이가 L인 평평한 땅이 필요하다. 3. 경사로를 겹쳐서 설치할 수 없다. 이 조건들만 조심해서 코드를 작성하면 된다. 먼저 첫 번째 조건은 간단하다. 경사로가 차이가 났을 때 둘의 차이가 2 이상 나는지 확인해주면 된다. 두 번째 조건은 생각보다 복잡하다. 먼저 경사로를 설치할 땅이 남아있는지 확인한다. 오르막 경사와..
문제: https://www.acmicpc.net/problem/14889 N명의 사람들이 스타트와 링크 팀으로 나누어 축구를 한다. (N은 2의 배수) 각 팀원들은 서로간의 시너지가 발생한다. 이것을 나타낸 능력치 표가 주어졌을 때 스타트 팀의 시너지 합과 링크 팀의 시너지 합이 최소가 되도록 했을 때 최소 값을 구하는 문제이다. N이 최대 20이므로 완전 탐색을 이용하면 되고 백트레킹으로 N/2명씩 두 팀을 계속 선택해가며 최소 값을 비교하면 된다. 끝. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include#includeusing namespace std;int n, arr[22][2..
문제: https://www.acmicpc.net/problem/14888 N개의 수로 이루어진 수열과 +, -, *, / 의 연산자 개수가 주어졌을 때 수 사이에 사용할 수 있는 연산자를 넣어보고 식의 결과 최대 값과 최소 값을 찾는 문제이다. 특이한 점은 연산은 *, / 먼저 하는게 아니라 왼쪽에서 오른쪽으로 순서대로 진행한다. 수열의 길이는 최대 10이므로 완탐을 해주면 된다. 백트레킹을 활용해 연산자를 n-1개 선택하고 계산 후 최대 값과 최소 값을 갱신하면 된다. 남아있는 연산자가 없는 경우 현재 연산자를 선택하면 안되고 사용 후 되돌려 놓을 땐 연산자 개수를 다시 올려 놓아야 한다. 이 문제의 함정아닌 함정은 범위이다. 10^-9 ~ 10^9 이므로 처음 max값과 min값을 초기화할 때 주의..
문제: https://www.acmicpc.net/problem/14503 로봇 청소기의 위치와 방의 구조가 주어졌을 때 로봇 청소기가 청소 할 수 있는 영역을 구하는 문제이다. 저번에 풀었던 로봇 청소기와 이름은 똑같지만 다른 문제이다. 시뮬레이션 문제이고 문제에서 주어진 행동을 코드로 작성할 수 있다면 어렵지 않은 문제이다. 특히 사각형 외곽은 모두 벽이라고 주어졌기 때문에 배열 범위 초과도 신경 쓸 필요가 없다. 방향은 0 1 2 3이 북 동 남 서 순서이기 때문에 현재 방향에서 왼쪽 방향을 보기 위해선 환형 배열이라고 가정했을 때 3칸 움직이면 된다. 즉 방향 d 가 있을 때 d = (d+3)%4를 하면 왼쪽 방향이 나온다. 끝. 1234567891011121314151617181920212223..
문제: 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 처음 점과 이 세 자리 순열을 이용해 도형을 만든다. 이때 주의해야할 점은 아래 -> 위, 왼 쪽 -> ..