KPU CE

문제 https://www.acmicpc.net/problem/2953 2953번: 나는 요리사다 "나는 요리사다"는 다섯 참가자들이 서로의 요리 실력을 뽐내는 티비 프로이다. 각 참가자는 자신있는 음식을 하나씩 만들어오고, 서로 다른 사람의 음식을 점수로 평가해준다. 점수는 1점부터 5 www.acmicpc.net 문제 해결 한 행을 입력받을 때마다 Max값을 갱신해가면서 만약 Max값이 바뀌면 인덱스 값도 바꿔가면서 그때 그때마다 갱신하는 식으로 풀었다. #include using namespace std; int main(void){ int Max = -1,idx; for(int i = 0;i a; temp +=a;} if(temp>Max){Max = temp;temp = 0;idx = i;}} c..

문제 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net X문자열과 Y문자열이 있다고 하자. X 문자열은 X(1)~X(i)까지 있다고 하고 Y문자열은 Y(1)~Y(j)까지 있다고 하자. X(i)와 Y(j)가 같은 경우와 다른 경우가 있을 수 있다. -만약 X(i)와 Y(j)가 같은 경우라면 X(1)~X(i-1), Y(1)~Y(j-1)의 LCS길이를 구하면 된다. 그리고 마지막 문자가 추가됨으로써 +1을 ..

문제 https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 문자열은 너무 어려운 것 같다. 일단 스택을 사용하여 입력받은 문자들을 스택에 다 넣고 top을 하면서 하나씩 꺼냈다. 만약 ')' 문자가 먼저 오지 않고 '('가 먼저 온다면 NO를 출력 '('와 ')'의 개수가 틀리면 틀리므로 NO를 출력하게 하였다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 ..

문제 https://www.acmicpc.net/problem/11719 11719번: 그대로 출력하기 2 입력이 주어진다. 입력은 최대 100줄로 이루어져 있고, 알파벳 소문자, 대문자, 공백, 숫자로만 이루어져 있다. 각 줄은 100글자를 넘지 않으며, 빈 줄이 주어질 수도 있고, 각 줄의 앞 뒤에 공백이 www.acmicpc.net 문자열에 약한것 같아서 풀어보게됬다. 문제 해결은 cin.getline 함수를 이용했다. cin함수는 공백및개행을 무시하는데 cin.getline함수는 공백및개행을 포함하므로 사용하게 되었다. cin.eof 함수는 bool 자료형을 반환하는데 만약 입력의 끝을 만나게 된다면 true를 반환한다. 코드 123456789#include using namespace std;i..

문제 https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제 풀이 일단 크게 두가지 경우로 나뉜다. 1. 시간이 초과되서 상담을 그날 상담을 못하는 경우 2. 시간이 초과되지 않아서 그날에 상담을 할 수 있는 경우 일단 1번의 경우이다. 상담을 한다면 N보다 초과되어서 이날의 상담은 하지 못하므로 이날의 최대 dp의 값은 i+1의 값이 된다. -> 이날 상담을 안하고 다음 날 한다. 2번의 경우 1.상담을 할 수 있..

문제 https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제 풀이 일단 크게 두가지 경우로 나뉜다. 1. 시간이 초과되서 상담을 그날 상담을 못하는 경우 2. 시간이 초과되지 않아서 그날에 상담을 할 수 있는 경우 일단 1번의 경우이다. 상담을 한다면 N보다 초과되어서 이날의 상담은 하지 못하므로 이날의 최대 dp의 값은 i+1의 값이 된다. -> 이날 상담을 안하고 다음 날 한다. 2번의 경우 1.상담을 할 수 있..

문제 https://www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 문제 해결 1. 그 자리에서 3을 점프뛰면 앞, 앞앞, 앞앞앞까지 탐색하는데 현재 dp의 값+1과 탐색한 자리에 dp값과 비교해서 작은 값을 선택한다. 2. 만약 그 자리가 끝이거나 넘어서면 결과값의 dp이므로 현재 자리의 dp값과 결과값dp를 비교해서 작은값이 결과값dp가 된다. 코드 12345678910111213141516171819202122232425262728293031..

문제 https://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net 문제 해결 1. 가장 긴 증가하는 부분 수열과 비슷하게 현재 자기 자신의 길이를 dp [i]에 저장했다. 2. A = {10, 30, 10, 20, 20, 10}인 경우에서 가장 긴 감소하는 부분 수열은 30, 20 , 10이다. 3. 처음 10은 뒤에 숫자가 없으므로 자동으로 dp[0] = 1이다. 4. 그다음 30..

문제 https://www.acmicpc.net/problem/2211 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다 www.acmicpc.net 문제 해결 1. 인접 리스트로 데이터들을 받는다. 2. 다익스트라 알고리즘을 실행한다. 3. 다익스트라 알고리즘에서 만약 new_val이 더 작으면 trace배열의 trace[next_node] = node 로 해준다. 4. 이렇게 해주면 해당노드의 최단거리의 부모를 알 수 있다. 5. trace배열을 각 노드들 별로 출력해준다. 코드 1234567891011121..

문제 https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 문제해결 1. 기존 BFS 문제에서 조금 변형된 문제이다. 나이트의 이동 방향를 ck함수에 추가한다. 2. 각 방향에 대해서 이동 가능/불가 여부를 판단한 후 큐에 넣어서 BFS알고리즘을 돌린다 3. 도착지의 x, y값이 나오면 BFS를 끝내고 다음 입력값에 BFS를 돌려주는 간단한 문제이다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21..