목록알고리즘/BOJ (28)
대웅짱님의 블로그
문제: https://www.acmicpc.net/problem/15684 오늘 문제는 사다리 조작이다. 사다리 타기 게임을 시뮬레이션 하는 문제이다. 내가 임의로 몇 개의 가로 선을 추가해서 i번 째 사다리를 i번 사다리로 통과하게 만들어야 한다. 만약 추가해야하는 가로 선이 3개가 넘어가거나 어떻게 가로 선을 놓아도 i번 째 사다리가 i번 사다리로 통과하지 못한다면 -1를 출력하고 가로 선을 추가해 위 조건을 만족시킬 수 있다면 그 가로 선의 개수의 최소 값을 출력하는 문제이다. (0개도 가능하다) 문제 해결 아이디어는 이전의 문제들 처럼 완전 탐색을 통해 풀었다. 가로 선은 최대 3개만 설치해야하고 사다리의 최대 개수와 높이가 각각 10, 30이므로 완전탐색을 이용해도 시간내에 충분히 가능하다. 먼..
문제: https://www.acmicpc.net/problem/15683 최대 8 x 8 크기의 사무실에 설치된 감시 카메라와 벽의 위치가 주어진다. 감시 카메라는 모두 5종류가 있고 최대 8 대 까지 설치 할 수 있다. 각 감시 카메라는 상 하 좌 우 방향으로 감시가 가능하다. 감시 카메라를 모두 작동시켰을 때 감시하지 못하는 최소한의 사각 지대 크기를 출력하는 문제이다. 문제에서 물어 보는 것은 최소한의 사각 지대 크기 이므로 각 감시 카메라의 방향에 따라 달라지는 사각 지대의 크기를 모두 구해야된다. 이전의 문제들 처럼 완전 탐색을 하면 된다. 백트레킹으로 각 카메라의 방향을 가지는 배열을 구해주고 방향과 감시 카메라 종류에 따라 감시 가능 지역을 칠해주고 최종적으로 남아있는 0(빈 칸)의 개수를..
문제: https://www.acmicpc.net/problem/2473 KOI 고등부 문제이다. 주어진 배열에서 세 숫자를 더했을 때 0과 가장 가까운 숫자들을 출력하는 문제이다. 처음엔 단순하게 생각해서 정렬된 배열 arr에서 arr[i] + arr[j] = k 라고 했을 때 lower_bound로 i+1 ~ j-1 구간에서 -k와 가장 가까운 수를 찾아 i, j, -k와 가장 가까운 수의 합으로 최소값을 갱신해 갈려고 했다. 하지만 계산해보면 O(N^2 * lg N) 이므로 5000*5000*12 = 3억이 나온다. 즉, 시간 초과다. 다른 방법을 찾다가 O(N^2)에 해결하는 방법을 찾아서 소개한다. 3-SUM이라는 알고리즘이다. 출처 위키: 3SUM 영어는 잘 모르겠고 간단하게 정렬된 배열 ar..
문제: 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..