private static void life()

예제 입력 1 3 3 5 1 3 2 4 8 1 1 2 예제 출력 1 RRDLLDRR - 모든 칸을 방문하면 된다. 첫번째 경우는 행의 개수가 홀수일 때, 두번째 경우는 열의 개수가 홀수일 때이다. (다른 요소가 짝수여도 상관없음을 확인할 수 있다.) - 그러나, 행/열의 개수가 짝수이면 1개 칸은 반드시 방문할 수 없다. 이는 체스판으로 증명 가능하다. 검정에서 출발하여 검정으로 가야만 하는데, 검정->흰색->검정->흰색-> ... -> 검정으로 도달하려면 반드시 1개의 흰색을 방문하지 못하게 된다. 따라서, 검은 칸이면서 + 가장 작은 수가 있는 칸을 방문하지 않으면 된다. - 풀이 Step 1) 문제의 조건에 따라 시작점을 (0,0), 끝점을(R-1,C-1)로 잡는다. 시작점을 이동시키는데, 끝점도 ..

예제 입력 1 4 2 2 예제 출력 1 2 1 4 3 https://www.acmicpc.net/problem/1201 1201번: NMK 1부터 N까지의 수를 한 번씩 이용해서 최대 부분 증가 수열의 길이가 M이고, 최대 부분 감소 수열의 길이가 K인 수열을 출력한다. www.acmicpc.net - 풀이 N = 10, M = 3, K = 4라고 가정하자. 1부터 N까지를 오름차순으로 적는다. (1, 2, 3, 4, 5, 6, 7, 8, 9, 10) K(최대 부분 감소 수열의 길이)만큼 그룹을 나눈다. ( [1 2 3 4] 5, 6, 7, 8, 9, 10) 모두 합하여 M개의 그룹이 되도록 나머지 그룹되지 않은 수를 그룹을 짓는다. ( [1 2 3 4] [5 6 7] [8, 9, 10] ) 각 그룹별로..

예제 입력 1 B ABBA 예제 출력 1 1 예제 입력 2 AB ABB 예제 출력 2 0 https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈이는 간단한 게임을 만들기로 했다. 두 문자열 S와 T가 주어졌을 때, S를 T로 바꾸는 게임이다. 문자열을 바꿀 때는 다음과 같은 두 가지 연산만 가능하다. 문자열의 뒤에 A를 추가한다. 문자열을 뒤집고 뒤에 B를 추가한다. www.acmicpc.net - BFS로 풀려면, 최악의 경우 S의 글자 ..

예제 입력 1 3 2 예제 출력 1 ABB 예제 입력 2 2 0 예제 출력 2 BA 예제 입력 3 5 8 예제 출력 3 -1 예제 입력 4 10 12 예제 출력 4 BAABBABAAB https://www.acmicpc.net/problem/12970 12970번: AB 첫째 줄에 문제의 조건을 만족하는 문자열 S를 출력한다. 가능한 S가 여러 가지라면, 아무거나 출력한다. 만약, 그러한 S가 존재하지 않는 경우에는 -1을 출력한다. www.acmicpc.net - A가 a개 있고, B가 b개 있으면(a+b == N) 0

예제 입력 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일 이후인 모든..