본문 바로가기

알고리즘

 (54)
[코드업] 5136 - No. X=Y=Z 세 정수 X,Y,Z 를 입력 받아 다음의 연산을 적용하여 X=Y=Z 가 되는 최소 연산의 횟수를 출력하는 프로그램을 작성하시오. 가능한 연산 X,Y,Z 중에서 2개를 선택하여 1 증가시킨다. X,Y,Z 중에서 1개를 선택하여 2 증가시킨다. 입력 첫 줄에 세 정수 X,Y,Z 가 입력된다. (0 X >> Y >> Z; int sum = X + Y + Z; int maxValue = max(X, max(Y, Z)); int minValue = min(X, min(Y, Z)); int midValue = sum - maxValue - minValue; cout
[백준] 14889 - 스타트와 링크 문제 오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다. BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 S[i][j]는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 S[i][j]의 합이다. S[i][j]는 S[j][i]와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 S[i][j]와 S[j][i]이다. N=4이고, S가 아..
[백준] 14888 - 연산자 끼워넣기 N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다. 예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다. 1+2+3-4×5÷6 1÷2+3+4-5×6 1+2÷3×4-5+6 1÷2×3-4+5+6 식의 계산은 연산자 우선 순위..
[코드업] 3705 - 연속된 구간의 최대합 어떤 수열이 있을 때 연속된 구간의 최대합을 출력하려고 한다. 예를 들어 2 -6 4 5 -2 6 2 -1이라는 수열이 있다면 연속된 구간의 최대 부분합은 15이다. (4+5+ -2 + 6 + 2) 더보기 입력 예시 8 2 -6 4 5 -2 6 2 -1 출력 예시 15 #include #include #include using namespace std; int main(){ int N; cin >> N; int sum = 0; int ret = -987654321; int num; for(int i = 0; i > num; sum += num; ret = max(ret, sum); if(sum < 0) sum = 0; } cout
[코드업] 3735 - LIS (Small) LIS(Longest Increasing subsequence)란 최장 증가 부분수열을 말한다. 프로그래밍 문제를 풀 다 보면 이것을 응용하는 문제가 많이 출제되고 있고, 동적계획법의 대표적인 사용 예 중 하나이다. 다음과 같은 원소의 개수가 8개(N)인 수열이 있을 때, 1 3 2 9 7 8 5 10 LIS = 1 2 7 8 10 으로 그 길이는 5이다. 더보기 입력 예시 8 1 3 2 9 7 8 5 10 출력 예시 5 #include #include using namespace std; int N; int arr[1001]; int dp[1001]; int search(int pos) { // pos에서 시작해서 최대길이 int& ret = dp[pos]; if (ret != 0) return ret..
[코드업] 3728 - 블럭 채우기 8 2∗1의 직사각형 블럭을 이용하여 4∗n 크기의 직사각형 모양으로 채우려고 한다. 가능한 방법의 수를 구하여라. 2∗1직사각형 블럭은 무한정 있다고 가정한다. 이 때 숫자가 커질 수 있으므로 100,007로 나눈 나머지를 출력하시오. #include using namespace std; const int DIV = 100007; int dp[10001] = {0, 1, 5,}; int block(int n){ if(dp[n] != 0) return dp[n]; int sum = 0; for(int i = 1; i < n; i++){ if(i == 1) sum += block(n - i); else if (i == 2) sum += block(n - i) * 4; else{ if(i % 2 == 0) su..
[코드업] 3721 - 블럭 채우기 7 2∗1의 직사각형 블럭을 이용하여 3∗n 크기의 직사각형 모양으로 채우려고 한다. 가능한 방법의 수를 구하여라. 2∗1 직사각형 블럭은 무한정 있다고 가정한다. 이 때 숫자가 커질 수 있으므로 100,007로 나눈 나머지를 출력하시오. #include using namespace std; const int DIV = 100007; int dp[10001] = {0, 0, 3,}; int block(int n){ if(dp[n] != 0) return dp[n]; if(n % 2 == 1) return dp[n] = 0; int sum = 0; for(int i = 2; i < n - 1; i += 2){ if(i == 2) sum += block(n - i) * 3; else sum += block(n ..
[코드업] 3719 - 블럭 채우기 6 2∗1과 1∗1의 사각형 블럭을 이용하여 2∗n 크기의 직사각형 모양으로 채우려고 한다. 가능한 방법의 수를 구하여라. 사각형 블럭은 무한정 있다고 가정한다. 이 때 숫자가 커질 수 있으므로 100,007로 나눈 나머지를 출력하시오. #include using namespace std; const int DIV = 100007; int dp[10001] = {0, 2, 7,}; int block(int n){ if(dp[n] != 0) return dp[n]; int sum = 0; for(int i = 1; i < n; i++){ if(i == 2) sum += block(n - i) * 3; else sum += block(n - i) * 2; } return dp[n] = (sum + 2) % DI..

티스토리툴바