![]()
문제 https://www.acmicpc.net/problem/5533 5533번: 유니크 첫째 줄에 참가자의 수 N이 주어진다. (2 ≤ N ≤ 200) 둘째 줄부터 N개 줄에는 각 플레이어가 1번째, 2번째, 3번째 게임에서 쓴 수가 공백으로 구분되어 주어진다. www.acmicpc.net 코드 n=int(input()) alist=[] blist=[] dlist=[] #ex)처음 플레이어의 숫자가 주어진다 플레이어 수는 5명이라고 하자 for i in range(n): gamelist=list(map(int,input().split())) #점수를 입력한다 #5명이 3번의 게임당 얻은 점수 """ 1번째 2번째 3번째 100 99 98 1번째사람이 3번게임해서 얻은점수 100 97 92 2번째사람이..
![]()
문제 https://www.acmicpc.net/problem/24041 24041번: 성싶당 밀키트 첫 번째 줄에 $N, G, K$가 공백으로 구분되어 주어진다. 두 번째 줄부터 $N$ 개의 줄 중 $i$ 번째 줄에는 $i$ 번째 재료에 대한 정보인 부패 속도 $S_i$, 유통기한 $L_i$와 중요한 재료인지를 나타내는 www.acmicpc.net Algorithm i에 대한 모든 S_i의 합이 G 이하이므로 가장 큰 x는 2e9이다. x의 최솟값은 0으로 해서 이진탐색으로 x를 찾는다. x일 이후에도 밀키트를 먹을 수 있으면 최솟값을 증가시키고 없다면 최댓값을 감소시키면서 x를 찾는다. Code import sys input = sys.stdin.readline N, G, K = map(int, in..
https://www.acmicpc.net/problem/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net 문제 도현이네 반 학생 N명의 이름과 국어, 영어, 수학 점수가 주어진다. 이때, 다음과 같은 조건으로 학생의 성적을 정렬하는 프로그램을 작성하시오. 국어 점수가 감소하는 순서로 국어 점수가 같으면 영어 점수가 증가하는 순서로 국어 점수와 영어 점수가 같으면 수학 점수가 감소하는 순서로 모든 점수가 같으면 이름이 사전 순으로 증가하는 순서로 (단, 아스키 코드에서 대문자는 소..
https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제요약 K개의 랜선의 길이가 주어진다. 이를 가지고 같은크기로 잘라서 N개의 작은 랜선을 만든다. 이때 만들 수 있는 최대의 길이를 출력한다. 문제 해결 유의해야할 점 랜선의 길이가 2^32-1까지 가능하다. int는 4byte이므로 양수는 2^16-1까지 가능하므로 더 큰 자료형을 써야했다. unsigned int를 사용했다. 1~(입력받은 랜선중 최대길이) 중에 ..
![]()
문제 n진수는 base가 n인 수를 말한다. 예를 들어 십진수는 base가 10인 수이다. n진수의 수 AmAm-1Am-2…A1A0를 n진수로 표현해보면 AmAm-1Am-2…A1A0 = Am × nm + Am-1 × nm–1 + Am-2 × nm–2 + … + A1 × n1 + A0 × n0이다. 예를 들면, 12468은 12468 = 1 × 104 + 2 × 103 + 4 × 102 + 6 × 101 + 8 × 100로 표현할 수 있다. 회문(Palindrome)이란 앞으로 읽으나 뒤로 읽으나 같은 글을 말한다. 예를 들면, madam, level, 12321은 회문이다. 반면에, Chung-ang이나 university, 54899는 회문이 아니다. 어떤 십진수의 수 A가 주어졌을 때, 이를 n진수로..
![]()
문제 왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다. 아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다. 아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오. 입력 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. 출력 일곱 난쟁이의 키를 오름차순으로 출력한다. 일곱 난쟁이를 찾을..
https://www.acmicpc.net/problem/15565 15565번: 귀여운 라이언 꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 www.acmicpc.net 코드 #include #include #include #include #include #include #include #include #include #include #include #define LL long long using namespace std; int main() { vector arr; int n; int k; cin >> n >> k; int num; for (int i = ..
![]()
문제 https://www.acmicpc.net/problem/17390 17390번: 이건 꼭 풀어야 해! [2, 5, 1, 2, 3]을 비내림차순으로 정렬하면 [1, 2, 2, 3, 5]이다. www.acmicpc.net Algorithm 수열을 비내림차순으로 정렬 후에 문제에서 주어지는 구간의 합을 출력하면 되는 문제이다. 구간의 합을 출력하면 되므로 누적합을 사용하였고, 비내림차순으로 정렬하기위해 .sort()함수를 사용하였다. 누적합을 사용할 수 있으면 쉽게 풀리는 문제였던것 같다. Code input = __import__('sys').stdin.readline n,q = map(int,input().split()) arr = list(map(int,input().split())) arr.so..
1806번: 부분합 (acmicpc.net) 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 문제유형 *누적 합 문제 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. 입출력 예제 (입력 1) 10 15 5 1 3 5 10 7 4 9 2 8 (출력 1) 2 풀이 1. N짜리 수열을 저장하는 arr배열과, 누적합을 저장하는 total배열을 만들어 준다. ..
![]()
문제 https://www.acmicpc.net/problem/13900 풀이 해당 문제는 누적합을 활용해서 풀 수 있다. 모든 경우의 수는 조합으로, nC2이다. 따라서, 시간이 부족하다. 단순 곱을 더하기만 하면 되는 경우이기에 분배 법칙과 누적 합을 활용하면 된다. 예를 들어, [1,2,3,4]인 경우 1*(2+3+4) + 2*(3+4) + 3*(4) 로 계산할 수 있는 것이다. 따라서, 괄호 안의 합은 누적합을 활용하면 된다. 아래 코드는 앞에서부터 계산한 누적합을 활용하기 위해, 분배법칙을 뒤에서부터 시행했다. 코드 N = int(input()) nums = list(map(int, input().split())) dp = [0]*(N+1) for i in range(N-1): dp[i+1] =..
문제 KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다. 같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다. 예를 들어, 주어진 용액들의 특성값이 [-2, 4, -99, -1, 98]인 경우에는 특성값이 -99인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액..
