live the life you love

문제의 조건은 간단했지만 dp와 dfs가 합쳐진 문제였다. 처음에 dp같지 않은 dp를 사용했더니 시간초과가 발생했다. dp[i][j]의 값을 i,j 위치에 판다가 있을 경우, 살 수 있는 최대일수 로 설정하였다. dfs의 탈출 조건을 설정해주는게 중요하다고 생각한다. if (dp[y][x] != 0) return dp[y][x]; dp[y][x]가 0이 아니라는 것은 해당 위치에 판다가 놓여졌을 때 살 수 있는 최대일수가 결정되었다는 뜻이다. 그러므로, [y][x]위치에 방문을 하였을 때 살 수 있는 일수를 계산하지 않고 그 값을 사용하면 되는 것이다. 소스코드 #include #include #define endl "\n" #define MAX 500 #define pii pair using name..

https://www.acmicpc.net/problem/1477 1477번: 휴게소 세우기 첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. N은 100보다 작거나 같으며, M도 100보다 작거나 같다. L은 100보다 크거나 같고, 1000보다 작거나 같다. 모든 휴게소의 위치는 중복되지 않으며, N+M은 L보다 작다. 둘째 줄에, 휴게소의 위치가 공백을 사이에 두고 주어진다. www.acmicpc.net 이분탐색을 활용하는 문제였다. 단순히 이분탐색 뿐 아니라 파라메트릭 서치를 사용하여야 한다. 물론 이 문제는 N의 값이 작아서, 이분탐색을 활용하지 않아도 된다. 문제는 현재 세워진 휴게소들 사이에 M개의 휴게소를 세우고 휴게소가 없는 구간의 ..

https://www.acmicpc.net/problem/1987 1987번: 알파벳 문제 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 www.acmicpc.net 백트래킹을 연습하기 위해 약 1달전, 2월 4일에 풀었을 때 틀렸던 문제를 다시 풀어보았다. 그때 트렐로에 남겨둔 메시지는 이랬었다. 두가지..

https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 처음에 문제의 조건을 꼼꼼하게 읽지 않아서 시간을 많이썼다. 시간을 많이 쓴부분은 다음과 같다. 궁수는 성에만 위치해야 한다. 궁수는 가장 가까운 거리의 적을 먼저 쏘고, 그 거리가 같은 적이 2명 이상이면, 가장 왼쪽의 적을 쏜다. 또한, 문제를 풀면서 궁수의 위치를 큐에 담아서 pop()을 하는 방식으로 다음 궁수의 행동을 하게했는데, 이렇게 하면 안됐었다. 이부분이 가장 시간을 많이 잡아 먹었다. 구현..

https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개의 자연수 A, B가 공백을 기준으로 구분되어 주어진다. 이는 A번 도시에서 B번 도시로 이동하는 단방향 도로가 존재한다는 의미다. (1 ≤ A, B ≤ N) 단, A와 B는 서로 다른 자연수이다. www.acmicpc.net 이차원 벡터를 만들고, 전형적인 bfs 탐색을 하는 문제였다. 시작지점과 연결되어있는 모든 정점을 방문하며, 기존에 방문하지 않은..

처음에는 어떤 유형의 문제인지 감을 못잡아서 2번 실패를 했다. 병사는 자신의 위치를 유지해야 하므로 따로 정렬을 하면 안되고, 그 안에서 내림차순으로 가는 가장 긴 수열을 찾아야 한다. 즉 LIS 알고리즘을 사용하면 된다. 이때, LIS는 최장증가부분수열이지만 이 문제는 숫자가 감소하는 길이가 가장 긴 것을 찾아야 하므로 최장감소부분수열을 찾으면 된다. LIS는 이중 for-loop을 사용하여 시간복잡도가 O(n^2)인 방법과 이분탐색을 사용하여 시간복잡도가 O(nlogn)인 방법이 있다. 이 문제는 N이 최대 2000이므로, O(n^2)의 시간복잡도를 가진 방법을 사용해도 무리가 없다. 소스코드 #include #include #define MAX 2000 using namespace std; int..

순열을 구하는 문제였다. N이 최대 8이므로, next_permutation을 사용해도 되지만, DFS로 순열을 구현하였다. N개의 순열을 구한 뒤, 매일 근손실이 얼마나 발생하는지 계산하고 500 미만이 되면 종료하였다. 루프를 다 돌때까지 500 미만이 되지 않으면 result 값을 1 증가시켰다.

https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다. 오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다. 파이프는 회전시킬 수 있으며, 아래와 같이 www.acmicpc.net 문제의 그림을 보면 현재 방향에따라 다음에 진행가능한 모양이 다르다. 현재 놓여진 파이프가 가로인 경우 가로 or 대각선으로..

https://www.acmicpc.net/problem/17406 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 값은 4이다. 1 2 3 2 1 1 4 5 6 배열은 회전 연산을 수행할 수 있다. 회전 연산은 세 정수 (r, c, s)로 이루어져 있고, 가장 왼쪽 윗 칸이 (r-s, c-s), 가장 오른쪽 아랫 칸이 (r+s, c+s)인 정사각형을 시계 www.acmicpc.net 입력 map에 배열을 입력받았다. 회전 연산의 정보는 따로 벡터에 담았다. 벡터에 구조체로 넣어서 하려고 했는데, 3개 이상의..

https://www.acmicpc.net/problem/5427 5427번: 불 문제 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다. 빌딩 www.acmicpc.net 입력 상근이의 위치와 불의 위치를 각각 큐에 저장하였다. 테스트 케이스가 있는 문제이므로, 테스트 케이스의 결과를 출력한 뒤 상근이의 위치가 ..