live the life you love

문제링크 : https://www.acmicpc.net/problem/10836 일반적인 시뮬레이션으로 풀었더니 시간초과가 났다. 입력의 최댓값이 100만이어서 그랬다. 문제 해결 조건 1번의 애벌레의 크기에 따라 나머지 애벌레의 크기가 바뀌는 것 조건 1번의 애벌레를 먼저 다 키운 뒤, 순차적으로 크기비교를 통해 남은 애벌레의 크기를 정해주면 되었다. 소스코드 #include #define endl "\n" #define MAX 700 using namespace std; int n, m; int zero = 0; int one = 0; int two = 0; long long arr[MAX][MAX]; long long backup[MAX][MAX]; void grow() { int y = n - 1..

https://www.acmicpc.net/problem/18430 18430번: 무기 공학 첫째 줄에는 길동이가 가지고 있는 나무 재료의 세로, 가로 크기를 의미하는 두 자연수 N, M이 주어진다. (1 ≤ N, M ≤ 5) 다음 N개의 줄에 걸쳐서, 매 줄마다 나무 재료의 각 위치의 강도를 나타내 www.acmicpc.net 전형적인 백트래킹으로 푸는 문제였다. 우선, 부메랑은 다음과 같이 4가지 모양을 가질 수 있고, 이를 최대한 많이 사용하여 최대 강도를 만들어 내야 한다. 문제 해결 방법 예를들어 첫번째 부메랑을 만들기 위해서는가운데(y, x)를 기준으로 (y,x-1) 과 (y+1, x)가 범위 내에 있어야 하고 (y,x-1)과 (y+1, x)가 사용된 적이 없어야 한다. 나머지 부메랑들도 마찬..

문제의 조건은 간단했지만 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 대각선으로..