목록알고리즘 (30)
대웅짱님의 블로그
문제: 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 처음 점과 이 세 자리 순열을 이용해 도형을 만든다. 이때 주의해야할 점은 아래 -> 위, 왼 쪽 -> ..
문제: 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 //상 우..