Twinparadox Factory

시간 제한 : 2초 메모리 제한 : 128MB 입력 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 출력 첫째 줄에 정답을 출력한다. 소스코드 #include #include #include using namespace std; int main(void) { int len, start, end; string str, substr=""; vector intArr; vector opArr; cin >> str; len = str.length(); start = 0; for (int i = 0; i < l..

시간 제한 : 1초메모리 제한 : 128MB 입력첫째 줄에 팀의 수 N, 카약이 손상된 팀의 수 S, 카약을 하나 더 가져온 팀의 수 R이 주어진다. (2 ≤ N ≤ 10, 2 ≤ S, R ≤ N)둘째 줄에는 카약이 손상된 팀의 번호가 주어진다. 팀 번호는 중복되지 않는다.셋째 줄에는 카약을 하나 더 가져온 팀의 번호가 주어진다. 팀 번호는 중복되지 않는다. 출력첫째 줄에 출발을 할 수 없는 팀의 최솟값을 출력한다. 소스코드#include #include using namespace std; int main(void) { int N, S, R, retire = 0; cin >> N >> S >> R; vector team(N + 1, 1); vector broken(S); vector spare(R); ..

시간 제한 : 2초메모리 제한 : 128MB 입력첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주어진다. 가격은 0보다 크거나 같고, 1,000보다 작거나 같은 정수이다. 출력첫째 줄에 김지민이 기타줄을 적어도 N개 사기 위해 필요한 돈의 최솟값을 출력한다. 소스코드#include #include using namespace std; int main(void) { int n, m, sum = 0; int package[50], piece[50]; bool cheap = false; cin >> n >> m; for (int i = 0; i < m; i++..

시간 제한 : 1초메모리 제한 : 128MB 입력첫째 줄에 N과 M이 주어진다. (1 ≤ M > n >> m >> j; start = 1, end = m; for (int i = 0; i > apple; if (start = apple) continue; if (start > ..

시간 제한 : 2초메모리 제한 : 128MB 입력첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 크거나 같고, N-i-1보다 작거나 같다. 출력첫째 줄에 줄을 선 순서대로 키를 출력한다. 소스코드 #include using namespace std; int main(void) { int n; int arr[10], ans[11] = { 0, }; cin >> n; for (int i = 0; i > arr[i]; ans[arr[0] + 1] = 1; for (int i = 1; i < n; i++) { int cnt = 0; fo..

시간 제한 : 2초메모리 제한 : 128MB 입력첫째 줄에 문자열 S가 주어진다. S는 백만보다 작은 길이 출력첫째 줄에 다솜이가 해야하는 행동의 최소값을 출력한다. 소스코드 #include #include using namespace std; int main(void) { string s; int len, zeropart = 0, onepart = 0, cnt = 0; cin >> s; len = s.length(); if (s[0] == '0') zeropart = 1; else onepart = 1; for (int i = 1; i < len; i++) { if (s[i] != s[i - 1]) { if (s[i] == '0') zeropart++; else onepart++; } } cout

Algorithm] Knapsack(배낭 문제) - 동적계획법 처음 내가 알고리즘 문제를 접했을 때 처음으로 배낭 문제를 접근했던 방식은 그리디였다.그리디는 다들 알고 있듯, 선택에 대한 번복도 없고, 근시안적인 선택으로 인해서경우에 따라서는 최적해를 보장하지 못하는 문제가 발생한다. 모든 배낭 문제에 대해서 그리디가 유효한 방법이 될 수 없는 건 아니고,물건을 임의로 쪼개어 담을 수 있는(용량을 정할 수 있는) 배낭 문제라면,무게 당 가격을 계산해서 적당히 담는 걸 고려하여 최적해를 구할 수 있기 때문에그리디 알고리즘으로는 해결이 가능하며 이를 부분 배낭(Fractional Knapsack)문제라고 한다.그러나, 일반적인 배낭 문제에서는 물건을 쪼개서 담을 수 없어서 다른 방식을 고려해야 한다. 이 때..

Algorithm] 작업 스케줄링(Task Scheduling) 기계에서 수행하는 n개의 작업(T1, T2, T3, ... , Tn)이 있고,각 작업에 시작 시간과 종료 시간이 존재한다고 할 때 최소한의 기계를 배치하면서모든 작업을 수행하도록 하는 문제를 작업 스케줄링이라고 한다.이 때 수행 시간이 중복되지 않게 모든 작업을가장 적은 수의 기계에 배정하는 최적해를 구하는 문제라는 것에 초점을 두자. 작업 스케줄링 문제에서 우리가 다룰 수 있는 변수와알 수 있는 정보에 대해서 조금 생각해보도록 하자. 작업의 수 n과, 각 작업들의 시작 시간과 종료 시간이 기본적으로 입력값으로 들어올 것이다.이건 입력값을 통해서 우리가 알 수 있는 정보고문제를 살펴봤을 때 우리가 알 수 있는 정보가 하나 더 있다.그 어떠한..