시간 : 10개 테스트케이스를 합쳐서 C의 경우 30초 / C++의 경우 30초 / Java의 경우 30초 / Python의 경우 30초
메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내
문제
25년 간의 수행 끝에 원재는 미래를 보는 능력을 갖게 되었다. 이 능력으로 원재는 사재기를 하려고 한다.
다만 당국의 감시가 심해 한 번에 많은 양을 사재기 할 수 없다.
다음과 같은 조건 하에서 사재기를 하여 최대한의 이득을 얻도록 도와주자.
1. 원재는 연속된 N일 동안의 물건의 매매가를 예측하여 알고 있다.
2. 당국의 감시망에 걸리지 않기 위해 하루에 최대 1만큼 구입할 수 있다.
3. 판매는 얼마든지 할 수 있다.예를 들어 3일 동안의 매매가가 1, 2, 3 이라면 처음 두 날에 원료를 구매하여 마지막 날에 팔면 3의 이익을 얻을 수 있다.
[입력]
첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스 별로 첫 줄에는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고,
둘째 줄에는 각 날의 매매가를 나타내는 N개의 자연수들이 공백으로 구분되어 순서대로 주어진다.
각 날의 매매가는 10,000이하이다.
[출력]
각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 최대 이익을 출력한다.
[예제 풀이]
1번째 케이스는 아무 것도 사지 않는 것이 최대 이익이다.
2번째 케이스는 1,2일에 각각 한 개씩 사서 세 번째 날에 두 개를 팔면 10의 이익을 얻을 수 있다.
입력
3
3
10 7 6
3
3 5 9
5
1 1 3 1 2
출력
#1 0
#2 10
#3 5
풀이
첫 번째 오답 : TC(4/10) 성공
import java.util.Scanner;
import java.io.FileInputStream;
class Solution
{
public static void main(String args[]) throws Exception
{
Scanner sc = new Scanner(System.in);
int T;
T=sc.nextInt();
for(int test_case = 1; test_case <= T; test_case++)
{
int N = sc.nextInt(); // 총 날짜 입력
int[] prices = new int[N];
int result = 0;
for (int n=0; n<N; n++) { // 매매가 입력
prices[n] = sc.nextInt();
}
for (int cur=0; cur<N; ) {
// 현재 idx 부터 뒤로 가장 큰 수를 찾아서
int max = prices[cur];
int maxIdx = cur;
for (int i=cur+1; i<N; i++) {
if (prices[i] > max) {
max = prices[i];
maxIdx = i;
}
}
// 현재 수가 가장 큰 수이면 break;
if (maxIdx == cur) break;
// 그 수 전까지 모두 구매
int stock = 0;
for (int i=cur; i<maxIdx; i++) {
stock++;
result = result - prices[i]; // 비용지불
}
// 그 수 때 판매
result = result + prices[maxIdx] * stock;
// 다음 수에 반복
cur = maxIdx+1;
}
System.out.printf("#%d %d\n", test_case, result);
}
}
}두 번째 오답 : TC(7/10) 성공
chatGPT가 짜준 답안
import java.util.Scanner;
class Solution {
public static void main(String args[]) throws Exception {
Scanner sc = new Scanner(System.in);
int T;
T = sc.nextInt();
for (int test_case = 1; test_case <= T; test_case++) {
int N = sc.nextInt(); // 총 날짜 입력
int[] prices = new int[N];
int result = 0;
for (int n = 0; n < N; n++) { // 매매가 입력
prices[n] = sc.nextInt();
}
int cur = 0;
while (cur < N) {
// 현재 날짜의 매매가가 최대값인 경우 판매
int maxIdx = cur;
for (int i = cur + 1; i < N; i++) {
if (prices[i] > prices[maxIdx]) {
maxIdx = i;
}
}
if (maxIdx > cur) {
// 현재 날짜부터 최대값까지 사서 팔기
int stock = 0;
for (int i = cur; i < maxIdx; i++) {
stock++;
result = result - prices[i]; // 비용지불
}
result = result + prices[maxIdx] * stock;
// 다음 인덱스로 이동
cur = maxIdx + 1;
} else {
// 현재 날짜가 최대값이라면 다음 날짜로 이동
cur++;
}
}
System.out.printf("#%d %d\n", test_case, result);
}
}
}세 번째 오답 : TC(6/10) 성공
첫 번째 코드의 result의 자료형을 long으로 고침
import java.util.Scanner;
import java.io.FileInputStream;
class Solution
{
public static void main(String args[]) throws Exception
{
Scanner sc = new Scanner(System.in);
int T;
T=sc.nextInt();
for(int test_case = 1; test_case <= T; test_case++)
{
int N = sc.nextInt(); // 총 날짜 입력
int[] prices = new int[N];
long result = 0;
for (int n=0; n<N; n++) { // 매매가 입력
prices[n] = sc.nextInt();
}
for (int cur=0; cur<N; ) {
// 현재 idx 부터 뒤로 가장 큰 수를 찾아서
int max = prices[cur];
int maxIdx = cur;
for (int i=cur+1; i<N; i++) {
if (prices[i] > max) {
max = prices[i];
maxIdx = i;
}
}
// 현재 수가 가장 큰 수이면 break;
if (maxIdx == cur) break;
// 그 수 전까지 모두 구매
int stock = 0;
for (int i=cur; i<maxIdx; i++) {
stock++;
result = result - prices[i]; // 비용지불
}
// 그 수 때 판매
result = result + prices[maxIdx] * stock;
// 다음 수에 반복
cur = maxIdx+1;
}
System.out.printf("#%d %d\n", test_case, result);
}
}
}아 다시 보니까 N이 최대 100만개라서 안되는건가 했더니
4(int크기) * 100만 = 400만바이트 < 256MB 라서 상관이 없었다.
도저히 실패하는 케이스를 모르겠어서 다시 뤼튼에 물어서 나온 코드를 돌려보니 통과가 됐다
정답코드
import java.util.Scanner;
class Solution {
public static void main(String args[]) throws Exception {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt(); // 테스트 케이스의 수
for(int tc=1; tc<=T; tc++) {
int N = sc.nextInt(); // 물건의 매매가를 알고 있는 일 수
int[] price = new int[N]; // 각 날의 매매가
for(int i=0; i<N; i++) {
price[i] = sc.nextInt();
}
long maxPrice = price[N-1]; // 현재까지의 최대 매매가
long profit = 0; // 이익
for(int i=N-2; i>=0; i--) { // 뒤에서부터 앞으로 이동
if(price[i] > maxPrice) { // 현재 매매가가 최대 매매가보다 크다면
maxPrice = price[i]; // 최대 매매가 갱신
} else { // 현재 매매가가 최대 매매가보다 작다면
profit += maxPrice - price[i]; // 이익 계산
}
}
System.out.println("#" + tc + " " + profit);
}
sc.close();
}
}뒤에서부터 해볼까라는 생각을 했었긴 하지만 내 코드가 왜 안되는건지 모르겠다
mattermost에 물어봐야지
자두과자