C++

문제 설명N(1 ≤ N ≤ 100)개의 수로 이루어진 1차원 배열이 있다. 이 배열에서 M(1 ≤ M ≤ ⌈(N/2)⌉)개의 구간을 선택해서, 구간에 속한 수들의 총 합이 최대가 되도록 하려 한다. 단, 다음의 조건들이 만족되어야 한다.각 구간은 한 개 이상의 연속된 수들로 이루어진다.서로 다른 두 구간끼리 겹쳐있거나 인접해 있어서는 안 된다.정확히 M개의 구간이 있어야 한다. M개 미만이어서는 안 된다.N개의 수들이 주어졌을 때, 답을 구하는 프로그램을 작성하시오.https://www.acmicpc.net/problem/2228      제한 사항      풀이문제를 요약하면, N개의 수를 M개의 구간으로 나누었을 대 구간에 포함된 수들의 합의 최댓값을 구하는 것이다.이때, 구간은 겹치면 안되며 정확히..

문제 설명민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다.단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다.N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오.https://www.acmicpc.net/problem/1339   ..

문제 설명역사, 그 중에서도 한국사에 해박한 세준이는 많은 역사적 사건들의 전후 관계를 잘 알고 있다. 즉, 임진왜란이 병자호란보다 먼저 일어났으며, 무오사화가 기묘사화보다 먼저 일어났다는 등의 지식을 알고 있는 것이다.세준이가 알고 있는 일부 사건들의 전후 관계들이 주어질 때, 주어진 사건들의 전후 관계도 알 수 있을까? 이를 해결하는 프로그램을 작성해 보도록 하자.https://www.acmicpc.net/problem/1613      제한 사항      풀이문제를 요약하면, K개의 (a, b) 쌍이 주어질 때 a가 b보다 먼저 일어난 사건을 의미한다.쿼리 S개를 입력받아 전후 관계를 판단하여 출력하면 된다. 우선 해당 문제는 다양한 방법으로 풀 수 있다.간단하게 모든 노드에서 출발하는 다익스트라를..

문제 설명보석 공장에서 보석 상자를 유치원에 기증했다. 각각의 보석은 M가지 서로 다른 색상 중 한 색상이다. 원장 선생님은 모든 보석을 N명의 학생들에게 나누어 주려고 한다. 이때, 보석을 받지 못하는 학생이 있어도 된다. 하지만, 학생은 항상 같은 색상의 보석만 가져간다.한 아이가 너무 많은 보석을 가져가게 되면, 다른 아이들이 질투를 한다. 원장 선생님은 이런 질투심을 수치화하는데 성공했는데, 질투심은 가장 많은 보석을 가져간 학생이 가지고 있는 보석의 개수이다. 원장 선생님은 질투심이 최소가 되게 보석을 나누어 주려고 한다.상자에 빨간 보석이 4개 (RRRR), 파란 보석이 7개 (BBBBBBB) 있었고, 이 보석을 5명의 아이들에게 나누어 주는 경우를 생각해보자. RR, RR, BB, BB, B..

문제 설명크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 값은 4이다.1 2 32 1 14 5 6배열은 회전 연산을 수행할 수 있다. 회전 연산은 세 정수 (r, c, s)로 이루어져 있고, 가장 왼쪽 윗 칸이 (r-s, c-s), 가장 오른쪽 아랫 칸이 (r+s, c+s)인 정사각형을 시계 방향으로 한 칸씩 돌린다는 의미이다. 배열의 칸 (r, c)는 r행 c열을 의미한다.예를 들어, 배열 A의 크기가 6×6이고, 회전 연산이 (3, 4, 2)인 경우에는 아래 그림과 같이 회전하게 된다.A[1][1] A[1][2] → A[1][3] ..

문제 설명상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀고 있다. 예를 들어, "8 3 2 4 8 7 2 4 0 8 8"에서 등식 "8+3-2-4+8-7-2-4-0+8=8"을 만들 수 있다.상근이는 올바른 등식을 만들려고 한다. 상근이는 아직 학교에서 음수를 배우지 않았고, 20을 넘는 수는 모른다. 따라서, 왼쪽부터 계산할 때, 중간에 나오는 수가 모두 0 이상 20 이하이어야 한다. 예를 들어, "8+3+2-4-8-7+2+4+0+8=8"은 올바른 등식이지만, 8+3+2-4-8-7이 음수이기 때문에, 상근이가 만들 수 없는 등식이다.숫자가 주어졌을..

문제 설명한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.다음 예는 22 × 22 크기의 배열을 방문한 순서이다.N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.다음은 N=3일 때의 예이다.https://www.acmicpc.net/problem/1074      제한 사항      풀이문제를 요약하면, $2^N x 2^N$ 크기의 배열이 주어지면, (r, c)를 몇 번째로 탐색하는지 구하는 것이다.이때, 탐색의 순서는 재귀적으로 z를 ..

문제 설명0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램을 작성하시오.행렬을 변환하는 연산은 어떤 3×3크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다. (0 → 1, 1 → 0)https://www.acmicpc.net/problem/1080      제한 사항      풀이문제를 요약하면, NxM의 크기의 행렬을 3x3만큼 뒤집는 연산을 통해 원본 행렬에서 결과 행렬로 몇 번의 연산만에 변환할 수 있는지 알아내야 한다. 처음에는 dfs혹은 bfs를 떠올렸다.하지만, 시간이나 메모리에서 문제가 있을 거라 생각했지만 일단 구현해 봤다.구현을 해보니 역시 메모리를 초과하여 에러가 발생했다. 해답은 간단했다.(0,0)에..

문제 설명민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다.어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다.https://www.acmicpc.net/problem/4195      제한 사항      풀이문제를 요약하면, 2명씩 입력이 주어질 때 두 사람은 친구 관계가 되며 친구가 되었을 때 이전 친구 관계를 포함하여 총 몇 명의 친구가 존재하는지 출력해야 한다. 문제 풀이는 간단하다.유니온-파인드를 이용하여 두 사람씩 친구 관계를 이어주면 된다. ..

문제 설명N개의 강의가 있다. 우리는 모든 강의의 시작하는 시간과 끝나는 시간을 알고 있다. 이때, 우리는 최대한 적은 수의 강의실을 사용하여 모든 강의가 이루어지게 하고 싶다.물론, 한 강의실에서는 동시에 2개 이상의 강의를 진행할 수 없고, 한 강의의 종료시간과 다른 강의의 시작시간이 겹치는 것은 상관없다. 필요한 최소 강의실의 수를 출력하는 프로그램을 작성하시오.https://www.acmicpc.net/problem/1374      제한 사항      풀이문제를 요약하면, N개의 강의를 진행하기 위해 사용해야 하는 최소한의 강의실의 개수를 구해야 한다. 해당 문제와 비슷한 문제로 강의실 예약 문제가 있다.강의실 예약 문제는 하나의 강의실을 최대한 많은 강의에 사용한다면 몇 개의 강의에 사용할 수..