junyCoding

https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다. 연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 www.acmicpc.net 문제를 읽었다면 알겠지만 바이러스 n(문제에서 입력값으로 주어짐) 개중에 m 개를 활성화로 선택한다. 이때 조건을 보면 활성화 바이..

문제를 보면 Cctv 5개가 있고 (1 ~ 5) 번 벽은 6으로 표현된다 먼저 문제를 이해해보면 1,3,4 번 Cctv는 총 4 가지 방법으로 감시할 수 있고 2 번은 2가지, 5 번은 1가지 밖에없다. 그럼 씨씨 티브이가 주어졌을 때 감시할 수 있는 모든 경우의 수를 구하면 된다. 예를 들어 2번과 3번과 5번이 주어졌다고 가정하자. 모든 경우를 각각 구한 후 감시할 수 있는 영역이 최대인 경우를 구하면 된다.(감시하지 못하는 영역의 최솟값을 구하는 문제) 2번은 (왼쪽, 오른쪽), (위, 아래) 두 가지! 3번은 4가지! 5번은 1가지! 나는 모든 경우를 탐색하기 위해서 재귀를 이용하였다. (숫자)는 Cctv 가 가리킬 수 있는 방향의 가짓수 중 하나라고 생각하고 설명하였다. 그럼 2번 Cctv 가 ..

나는 이문제를 다이나믹 프로그래밍으로 접근해서 풀었다. dfs 풀이법도 있으니까 나중에 찾아서 공부해야겠다. 1. 일단 첫 번째 나는 dp로 풀기로 결정했기 때문에 dp 배열을 만들어준 후 각 인덱스(0을 제외한) 에 해당하는 배열 값(dp [i])을 i 일에 벌 수 있는 최대 수익이라고 놓았다. (d [i] => i 일에 벌 수 있는 최대 수익) 점화식은 간단하게 구할 수 있다. 예를 들어 3일째 벌 수 있는 최댓값(dp [3]) 를 구하기 위해서는 (1 일대에 벌 수 있는 최대값 + 3일째벌수있는 값), (2 일째에 벌수있는 최대값 + 3일째 벌수있는 값) 중 가장 큰 값을 구하면 된다 dp[i] = Math.max(dp[i], dp[j] + p[i]); 2. 하지만 생각해야 할 조건이 2 가지 정도..

출처: https://www.acmicpc.net/problem/13458 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net 문제를 읽어 보면 그리디 문제라는 것을 알 수 있다.!! N 개의 시험장과 각 시험장에 응시하는 인원이 주어진다. 그다음에는 총감독관과 부감독관이 감시할 수 있는 인원이 주어진다 문제 조건에서 각 방마다 총감독관은 1명이 있어야 하고 부감독관은 여러 명 있어도 된다! !! 주의할 점은 총 감독할 수 있는 인원의 최솟값이 너무 커질 수..

스타트와 링크 문제를 정리 해보자면 1. N 명의 팀원을 두팀으로 나눈다(문제에선 N 이 짝수로만 주어진다.) 2. 두팀(A 팀 ,B 팀) 으로 나누어 졌을때 각팀원들의 능력치의 합을 구해 A팀의 능력치의 합 과 B팀의 능력치의 합의 차이를 최소화 하는것이다. 3. 위 2번에서 헷갈리지 말아야하는 부분은 예를들어 1번과 2번이팀이고 3번과 4번이 팀이라고 가정하자 1, 2 번이 속한 팀의 능력치의 합 : 1번이 2번을 만나 능력치 10 을 얻었다고 가정하자 (위배열로 예를 들면 arr[1][2] ) 2 번은 1번을 만나 능력치 8 을 얻었다고 가정하자 (마찬가지로 arr[2][1]) 즉 1, 2 번이 속한 팀원들의 능력치의 합은 10 (arr[1][2]) + 8 (arr[2][1]) = 18 이다. 4...