private static void life()

예제 입력 1 100 50 예제 출력 1 48 예제 입력 2 1 1 예제 출력 2 1 예제 입력 3 17 5 예제 출력 3 4 예제 입력 4 2 4 예제 출력 4 2 예제 입력 5 20 4 예제 출력 5 4 https://www.acmicpc.net/problem/1783 1783번: 병든 나이트 첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net - N/M 제한이 2,000,000,000이므로 직접 돌려볼 수는 없다. - 이동할 수 있는 케이스는 모두 오른쪽으로 이동하는 것 밖에 없으므로 그냥 계산을 통해 구한다. - Row가 1이면 이동 불가능 == 1 (자기 자신도 세라고 했으므로) - Row가 ..

예제 입력 1 30 예제 출력 1 30 예제 입력 2 102 예제 출력 2 210 예제 입력 3 2931 예제 출력 3 -1 https://www.acmicpc.net/problem/10610 10610번: 30 문제 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다. 미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라. 입력 N을 입력받는다. N는 최대 105개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다. 출력 미르코가 만들고 싶어하는 수가 존재한다면 그 수를 출력하라. 그 수가 존재하지 않는 www.acmicpc.net - 30을 ..

예제 입력 1 4 -1 2 1 3 예제 출력 1 6 힌트 (-1)+1+(2*3)=6 https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다. 하지만, 같은 위치에 있는 수(자기 자신)를 묶는 것은 불가능하다. 그리고 어떤 수를 묶게 되면, 수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더한다. 예를 들면, 어떤 수열이 {0, 1, 2, 4, 3, 5}일 때, 그냥 이 수열 www.acmicpc.net - 양수는 큰 수끼리 묶고, 음수는 작은 수 끼리 묶..

예제 입력 1 55-50+40 예제 출력 1 -35 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. www.acmicpc.net - (-) 부호가 등장하는 시점부터 괄호로 묶으면 뒤에 나오는 것들은 모두 마이너스로 계산하여 더하면 된다. 10+20-(30+55-50+40+30)-(40) #include char input[51]; int main(void) { scanf("%s", input); int idx..

예제 입력 1 6 10 20 10 30 20 50 예제 출력 1 4 https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net - N제한이 너무 크기 때문에, 다이나믹 알고리즘으로는 풀 수 없다. - 따라서, 1차원 배열을 이용해 lower_bound()로 현재 A 원소와 같거나 더 큰 D 원소를 찾아, 존재하면 덮어쓰고 없으면 추가해주는 방식으로 "길이만" 정확하게 구할 수 있다. #include #include #include const int MAX..

예제 입력 1 7 20 1 2 1 10 3 100 2 8 2 5 20 50 10 예제 출력 1 185 https://www.acmicpc.net/problem/2109 2109번: 순회강연 문제 한 저명한 학자에게 n(0≤n≤10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1≤d≤10,000)일 안에 와서 강연을 해 주면 p(1≤p≤10,000)만큼의 강연료를 지불하겠다고 알려왔다. 각 대학에서 제시하는 d와 p값은 서로 다를 수도 있다. 이 학자는 이를 바탕으로, 가장 많은 돈을 벌 수 있도록 순회강연을 하려 한다. 강연의 특성상, 이 학자는 하루에 최대 한 곳에서만 강연을 할 수 있다. 예를 들어 네 대학에서 제시한 www.acmicpc.net - 5일이면 기한이 5일 이후인 모든..

예제 입력 1 3 2 1 65 5 23 2 99 10 2 예제 출력 1 164 - 두 가지 방법으로 풀이가 가능하다. 1) 각각의 보석을 기준으로, 보석이 어떤 가방에 들어가면 좋을까? 가격이 높은 순으로 들어갈 수 있는 가장 작은 가방에 넣고 그 가방을 지운다. 2) 각각의 가방을 기준으로, 어떤 보석이 들어가면 좋을까?? [ 풀이 1) ] #include #include #include #include const int MAX_SIZE = 300000; using namespace std; class Jewel { public: int m; // 무게 int v; // 가격 }; multiset bag; int N; int K; int main(void) { scanf("%d %d", &N, &K);..

예제 입력 1 3 HHT THH THT 예제 출력 1 2 https://www.acmicpc.net/problem/1285 1285번: 동전 뒤집기 첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위를 향하도록 놓인 경우 H, 뒷면이 위를 향하도록 놓인 경우 T로 표시되며 이들 사이에 공백은 없다. www.acmicpc.net - 각 행/열 별로 동전을 뒤집을 수 있다. 행렬/전구와 스위치 문제와 유사 - 각 동전의 상태에 영향을 미칠 수 있는 동작은 2가지 이다. (그 행에 속하는 행 뒤집기, 그 열에 속하는 열 뒤집기) - 그런데, 이미 모든 행에 대해서 뒤..

예제 입력 1 3 000 010 예제 출력 1 3 https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는(1) 상태와 꺼져 있는 (0) 상태 중 하나의 상태를 가진다. i(1

예제 입력 1 3 4 0000 0010 0000 1001 1011 1001 예제 출력 1 2 https://www.acmicpc.net/problem/1080 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net - 여기서, A행렬에서 모두 가능한 3x3 Flip 연산을 하느냐/하지 않느냐로 Brute Force를 돌리면 2^NM (실제로는 2^(N-2)(M-2)) 이라는 어마어마한 시간 복잡도가 나오기 때문에 이 방법으로는 해결 불가능하다. - 여기서, 핵심은 (0,0) 부분이 다르다면, (0,0) 부분을 변경하도록 해야 하는..