live the life you love

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 입력 상근이의 위치와 불의 위치를 각각 큐에 저장하였다. 테스트 케이스가 있는 문제이므로, 테스트 케이스의 결과를 출력한 뒤 상근이의 위치가 ..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. www.acmicpc.net 벽을 세울 수 있는 위치를 찾기 위해 next_permutation을 사용하였다. 연구소의 크기가 최대 8X8이고, 벽은 3개를 세워야 하..

https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다. 로봇 청소기는 다음 www.acmicpc.net 그렇게 어려운 시뮬레이션은 아니었는데 문제를 잘못 읽어서 좀 헤맸다. 'd가 0인 경우에는 북쪽을, 1인 경우에는 동쪽을, 2인 ..