C++105 [C++] 백준 11399번 : ATM https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제 풀이 배열에 값들을 입력받고 정렬한다. 현재 최적의 값은 대기시간이 가장 짧을 때 이므로 처리시간이 짧은 순서대로 오면 되기 때문에 정렬하는 것이다. 두 가지 풀이법이 있다. 1. 대기 시간을 따로 계산해서 총 걸린 시간에 더한다. 2. 덧셈이 반복되기 때문에 총 걸린 시간은 i번째 값 * n-i 번이다. 느낀 점 쉬운 문제였지만 제출 이후에 다르게 구성할 방법을 생각해보았다. 코드 #include #include usi.. 2021. 6. 28. [C++] 백준 1931번 : 회의실 배정 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 풀이 그리디 알고리즘의 원리인 "현재 가장 좋은 것 고르기"에 기반해서 생각하면 최대 개수는 다음 회의까지 공백이 가장 짧을 때이다. 구조체로 구현한 배열은 회의 시간의 시작과 종료시간을 저장한다. STL에서 지원하는 sort 함수를 활용해서 배열의 종료시간을 기준으로 내림차순으로 정렬한다. 내림차순으로 정렬하는 이유는 공백 시간을 종료 시간으로 따질 것이기 때문이다. 또한, 정렬되어있는 배열을 통해서 i번째 회의의 시작 시간이 이전 회의의 종료 시간보다 크거나 같을 때를 따지기 때문에 회의의 개수를 따지기.. 2021. 6. 27. [C++] 백준 11047번 : 동전 0 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 문제 풀이 그리디 알고리즘은 현재 가장 최적의 것부터 사용하는 알고리즘이다. 동전 개수가 최소가 되려면 가장 큰 것부터 따지면 된다. 느낀 점 그리디 알고리즘의 시작이다! 문제 자체가 쉬워서 최대한 이쁘게 코드를 짜고 싶었다. 제출하고 보니 지저분 한 것 같기도 하다. 코드 #include #include using namespace.. 2021. 6. 26. [C++] 백준 12865번 : 평범한 배낭 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제 풀이 배열 DP[i][j]는 가방이 j 무게 일 때 i 번째 물건까지 확인했을 때의 최대 가치이다. 예를 들어서 DP[3][5]는 무게 5인 가방에 대해서 3번째 물건까지 확인했을 때의 최대가치이다. 경우는 단순하게 2가지로 i번째 물건을 담았을 때와 담지 않았을 때로 나뉜다. 표를 통해서 이해하면 매우 쉽다. (문제 참고!).. 2021. 6. 25. [C++] 백준 1912번 : 연속합 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제 풀이 연속합을 구하는 문제이기 때문에 경우는 단순하게 2가지 경우로 나뉜다. 1. i번째 더한 값이 최대인 경우 2. i-1번째까지 더한 값보다 i번째 값이 더 큰 경우 배열 DP[i]는 i번째 연속합을 저장한다. DP[i]는 2가지 경우에 따라 DP[i-1] + arr[i]값과 arr[i]값만 비교해주면 된다. 느낀 점 처음에 DP[i]의 값에 대해서 잘못 생각해서 많이 헤매었다. i번째까지 존재하는.. 2021. 6. 25. [C++] 백준 9251번 : LCS https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제 풀이 10844번:쉬운 계단 수와 문제와 비슷한 문제이다. 2차원 배열 DP[i][j]는 첫 번째 문자(str1)의 i번째와 두 번째 문자(str2)의 j번째까지 가장 긴 부분 수열의 길이를 저장한다. 즉, DP[2][3]은 AC와 CAP를 비교했을 때의 LCS의 길이가 1이라는 것이다. (ex. DP[4][5] == 2) 배열 DP의 원소를 채우.. 2021. 6. 25. 이전 1 ··· 10 11 12 13 14 15 16 ··· 18 다음