문제 분석https://www.acmicpc.net/problem/15683n*m 배열이 주어진다. 각 배열의 원소는 값에 따라 아래의 역할을 한다. 0 : 빈 땅1~5 : CCTV6 : 벽 각 CCTV는 1~5의 값에 따라 감시할 수 있는 방향의 유형이 정해져있고, 특정 방향으로 바라보는 CCTV는 배열의 끝 혹은 벽을 만나기전까지 감시를 할 수 있다. CCTV의 방향은 아래와 같다. CCTV는 90도씩 회전할 수 있다. 이때, CCTV들을 특정 각도로 회전시키며 배열을 감시할 때 사각지대의 최솟값을 구하는게 문제다. 여기서 주의할 점은, 벽과 CCTV가 존재하는 곳은 사각지대로 세지 않는다. 문제를 객체지향적으로 접근한다면, 즉 조금 더 세분화해서 쪼개보면 각 CCTV를 조금 더 단순하게 표현할 ..
문제 분석https://www.acmicpc.net/problem/2531 회전 벨트 위에 초밥이 있고, 각 초밥은 종류가 존재한다.손님은 k개 연속으로 초밥을 먹는다.이때, 보너스로 c 종류 초밥을 하나 더 공짜로 먹는다. 그렇다면, 손님이 먹은 초밥의 종류의 최댓값은 얼마인가 ? 손님은 0~k, 1 + 1+k .. 의 초밥을 연속해서 먹는다.이때, n-1,0,1 .. 이런 순서로도 먹을 수 있다. 처음과 두번째 경우를 비교하면, 1~k까지의 초밥은 공통으로 먹게된다.따라서, 굳이 이걸 반복해서 다시 찾을 필요가 없다. 즉, 처음 먹은 0~k개의 초밥에 대해서 그 종류들과 각 종류 별 count를 저장하고두번째부턴 0번째 먹은 초밥을 빼고, k+1번째 초밥을 더하면 된다. 따라서, 매 반복에서 현재 초..
문제 분석https://www.acmicpc.net/problem/1522a와 b로 이루어진 문자열이 주어진다.주어진 문자열에서 원소들을 swap하여 a를 모두 이어붙이고자 한다.이때, 주어진 문자열의 맨 앞과 맨끝은 붙어있는 형태, 즉 원형이라고 할 때 a를 모두 이어붙이기 위한 최소 swap 수는 ? 문제를 어렵게 생각하면 미궁에 빠질 수 있지만,, 조금 더 간단하게 생각해보자 우선, 맨 앞과 맨 뒤는 이어져 있다. 그렇기에 배열에서 굳이 떨어트려놓을 필요가 없다.따라서 아래처럼 문자열을 바꿔서 생각을 해보자abababababababa => aababababababab 어떤게 가장 효율적으로 a,b를 스왑하게 되는걸까 ? 이미 맨뒤의 a들을 맨 앞으로 옮겨놨으니 사실 원형이라는 조건은 이제 잊어도된다..
문제 분석https://www.acmicpc.net/problem/1976N개의 도시와 각 도시와 연결된 도시들에 대한 정보가 주어진다.M개의 도시 방문 경로가 가능한 경로인 지 확인하여 가능하다면 YES 아니면 NO를 반환하면 되는 문제다, 여기서 경로에 대해 최적인지 판단할 필요가 없다.따라서, 두 도시 사이에 어떠한 길이의 경로로든 연결만 되어 있다면 갈 수 있게 된다. 그렇기에 union find로 각 도시의 부모를 하나 정하고 두 도시의 부모 idx가 동일하면 같은 집합임을 의미하고 이는 곧 서로의 도시로 갈 수 있다는 뜻이 된다. 주의할 점은, m개의 방문 도시를 0,1, .. 이렇게 주는게 아닌, 1,2,... 이렇게 주니 인덱스를 애초에 1부터하던가 아니면 M개의 도시의 인덱스를 1 빼고 ..
문제 분석https://www.acmicpc.net/problem/22866N개의 배열에 대해 i번째 원소의 왼쪽 (0~i-1)과 오른쪽 (i+1 ~ n-1) 에 대해서 각각i번째 원소의 값보다 큰 원소를 i번째 원소가 볼 수 있다.왼쪽을 쳐다보는 기준 a 0번째 빌딩부터 오른쪽으로그리고 마지막 빌딩부터 0쪽 방향, 즉 왼쪽으로 2번에 걸쳐서 탐색하며 문제를 해결했다. 스택에 순차적으로 빌딩을 삽입하고i번째 빌딩보다 높은 빌딩만 남겨둔다면결국 스택의 크기가 i번째 빌딩이 볼 수 있는 빌딩의 수가 되고스택의 peek의 값이 가장 최근에 삽입된, i와 가장 가까운 볼 수 있는 빌딩이 된다. 이를 왼쪽 -> 오른쪽, 오른쪽 -> 왼쪽으로 한 번씩 탐색하면 i의 입장에서 볼 수 있는 빌딩의 수와 가장 가까운 i..
문제 분석https://www.acmicpc.net/problem/4179n*m의 미로에서 1명의 지훈이와 x개의 불이 주어진다.땅은 . 벽은 # 지훈이는 J 불들은 F로 표현된다.미로의 가장자리에선 1의 시간을 소모하여 탈출할 수 있다. 최소의 탈출 가능 시간을 구하고, 만약 탈출이 불가능하면 IMPOSSIBLE을 리턴하면 된다. 전형적인 bfs문제다. 불과 지훈이는 동시에 이동한다. (사실상 불이 먼저 이동하고 지훈이가 이동하는게 합리적이다)따라서, 불, 지훈이에 대한 queue를 담고 각자 상하좌우에 대해 가능한 경로를 탐색해나간다,이때, 불의 이동으로 인해 갈 수 있었던 땅이 F로 변하게 되므로 이를 반영해주면 지훈이가 이동하는 차례에 .만 이동 대상으로 탐색하면 되어 부가적인 로직 없이 처리할 ..
문제 분석https://www.acmicpc.net/problem/1027N개의 원소가 주어진다.각 원소는 빌딩의 높이를 의미한다.i번째 빌딩에서 j번째 빌딩이 보인다는 뜻은 두 빌딩의 꼭대기를 포함하는 직선에 그 사이의 다른 빌딩이 접하거나 만나지 않아야 한다는 것이다.이때, 가장 많은 빌딩이 보이는 빌딩에서 볼 수 있는 빌딩의 수를 구해야 한다. 처음에는, 전체 배열 중 가장 높이가 높은 값을 기준으로 LIS를 왼쪽에서 TOP 오른쪽에서 TOP해서 두번 구하는 방식으로 풀어보려 했으나.. 문제의 조건이 단순히 높이가 낮으면 보이는 것이 아닌 두 빌딩을 이은 선분에 맞닿는 빌딩이 없어야 보인다는 것이었기에 LIS로는 해당 조건을 만족시키기 꽤 어려웠다. 근데, N 자체가 50밖에 되지 않는다. 즉, n..
문제 분석https://www.acmicpc.net/problem/2138N가능한 최소의 스위치 조작으로 주어진 전구 배열을 정답 배열로 만들려하는데 이때 드는 비용(횟수)을 구하는 문제이다. 처음 시도한 풀이는 아래와 같다.맨 마지막 2개의 전구에 대해서 그 앞의 전구까지 가능한 최소의 비용으로 스위치 조작을 해서 정답 배열과 일치시켜 오게 된다면 이를 3개짜리 전구를 조작하는 문제로 변경할 수 있다고 생각했다.즉, 1010111000 -> 00000000 이런 배열에 대해서 결국에는 0 a b -> 0 0 0 이 상태가 되는 문제로 변경할 수 있게 된다.따라서 3개의 전구에 대해서 각각 최소의 스위치 조작으로 정답 배열과 일치시킬 수 있다면 해당 횟수를, 없다면 -1을 리턴하는 방식으로 구현했었다. ..
