KPU CE

문제 https://www.acmicpc.net/problem/13398 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제 해결 기존의 연속합 문제에서 변형을 하였다. 기존의 연속합 문제 + 제거할 경우를 생각 했다. 제거 dp를 따로 만들어서 저장했고 dp의 값은 전 값을 제거한 값,그냥 전의 dp값을 받는 경우 2가지를 생각해서 두 값의 max값을 넣어 주었다. 코드 12345678910111213141516171819202122232425#include #include using namespace std;..

문제 https://www.acmicpc.net/group/board/view/9362/19864 로그인 www.acmicpc.net 문제해결 다이나믹 프로그래밍으로 풀었다. fibo(n) = fibo(n-1) +fibo(n-2) 이라는 식을 규칙을 보고 유추하여서 배열로 구현하였다. 코드 #include #pragma warning(disable : 4996) int main(void) { int n; long long int ary[92]; ary[0] = 0; ary[1] = 1; scanf("%d",&n); for (int i = 2; i

문제 https://www.acmicpc.net/problem/2747 2747번: 피보나치 수 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 문제 해결 재귀를 이용하여 0이면 0을 리턴하고 1이면 1를 리턴하고 그외는 n-1,n-2의 함수를 호출하여 구현했다. 코드 #include using namespace std; int fibo(int n){ if(n == 1){return 1;} else if(n == 0){return 0;} return (fibo(n-1)+fibo(n-2)); } int ..

문제 https://www.acmicpc.net/problem/2167 2167번: 2차원 배열의 합 첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 www.acmicpc.net 문제 해결 입력받은 그대로 반복문을 만들어서 풀었다. 코드를 보면 이해가 될 것이다. 코드 #include using namespace std; int N,M,map[302][302]; int solve(int x,int y,int dx,int dy){ int result = 0; for(int i = y;i N >> M; for(int i = 1;i map[i]..

문제 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/2743 2743번: 단어 길이 재기 알파벳으로만 이루어진 단어를 입력받아, 그 길이를 출력하는 프로그램을 작성하시오. www.acmicpc.net 문제 해결 파이썬으로 풀었고 len 함수를 써서 간단하게 풀었다. 코드 print(len(input()))

문제 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.상담을 할 수 있..