[D2] 1859. 백만 장자 프로젝트

[GeonHui2]

문제 링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LrsUaDxcDFAXc

풀이 사항

풀이 일자: 2024.00.00
풀이 시간: 00분 00초
채점 결과: 오답/시간 초과/런타임 에러/정답
예상 문제 유형: 구현/BFS/DFS/DP/자료구조/문자열 등

풀이 방법

(풀이 접근 및 방법에 대한 설명)

[GeonHui2]

문제 링크

#6

풀이 사항

풀이 일자: 2024.01.13
풀이 시간: 10분
채점 결과: 정답
예상 문제 유형: 구현

풀이 방법

• 문제를 읽고 최대 이익을 얻을 수 있는 방법을 먼저 생각해 보았다.
• 케이스를 역순으로 입력받은 후 이전에 저장했던 가격보다 가격이 낮으면 이익에 더하고 가격이 높으면 새롭게 저장하는 방식을 통해서 최대 이익을 얻을 수 있었다.
• N 개의 배열을 만들고 입력을 배열의 끝에서부터 받았다.
• 그 후 저장하는 값을 0으로 선언 후 배열을 반복문을 통해서 저장하는 값보다 높으면 저장하는 값을 변경하고 낮으면 저장한 값에서 현재 가격의 차를 결괏값에 더하였다.

[skdudddl]

문제 링크
#12

풀이 사항
풀이 일자: 2024.01.14
풀이 시간: 30분
채점 결과: 정답
예상 문제 유형: 구현

풀이 방법

• 먼저 DP처럼 (현재가격 *개수 - 이전비용들의 합)으로 계산하고 max값을 구할려고 했다.
• 그런데 테케가 맞지 않아서 다시 생각해야했다.
• 그래서 현재가격보단 최대값을 생각해야했고 앞보다는 뒤의 최대값을 우선으로 생각해야했다.
• 그래서 N개의 배열을 입력받은 후, 최대값을 뒤에서 찾도록 반복문을 구현했다.
• (최대값 *개수 - 이전비용들의 합)을보다는 (최대값 - 해당 가격) 구한 후 해당 갯수 만큼 더했다.

[ensk26]

문제 링크

#17

풀이 사항

풀이 일자: 2024.01.16
풀이 시간: 40분
채점 결과: 정답
예상 문제 유형: 구현

풀이 방법

• 완전 탐색을 이용해 시도를 했지만 숫자와 길이가 너무 커 동작하는 시간이 오래 걸렸다.
• 그래서 뒤쪽부터 읽으면서 가장 큰 숫자를 찾아가면서 각 칸의 가장 높은 수익을 얻는 값을 더했다.
• 숫자 범위가 커서 int, double로는 값이 제대로 나오지 않아 long으로 수정했다.
• 앞으로 숫자 단위도 관심을 가지는 버릇을 만들어야 할 것 같다.

[jisooolee]

문제 링크

#20

풀이 사항

풀이 일자: 2024.01.14
풀이 시간: 1시간 45분
채점 결과: 시간 초과
예상 문제 유형: 구현

풀이 방법

• 이중 반복문을 이용해 완전 탐색을 시도하였다.
• 첫 번째 안쪽 반복문을 돌면서, 검사하지 않은 물건 값 중 가장 큰 값, max를 찾는다.
• 두 번째 안쪽 반복문을 돌면서, max 바로 직전까지 물건 값들의 차를 result에 더해준다.
• 배열의 모든 값을 검사할 때까지 계속해서 반복문을 실행한다.
• 하지만 결국 시간 초과 엔딩...

[ramrami-B]

🔗 #22

💪🏻 풀이 사항

📅 풀이 일자: 2024.01.17
⏰ 풀이 시간: 30분 36초
🥺 채점 결과: 정답✅
💡 예상 문제 유형: 구현

✍🏻풀이 방법

처음에는 아래와 같은 방법으로 구현 하였다.

1. 매매가를 담은 배열 salePrices를 뒤에서부터 접근한다.
2. 현재 접근한 인덱스에서 한 칸씩 앞으로 이동하며 비교할 때, 앞에 있는 인덱스 중 현재 값보다 더 낮은 값이 있다면 그 갯수만큼 cnt++하고 더 큰 값이 나오면 종료한다.
3. cnt한 만큼 현재 접근한 인덱스의 값과 곱해서 answer에 더하고 참조했던 낮은 값들을 빼준다, 멈춘 곳에서 앞에 값들이 남아있다면 다시 앞의 값과 비교해서 2번 반복

그런데 생각보다 cnt++를 하는 것과 낮은 값들을 하나 하나 빼는 과정이 번거로웠고, 예시 input으로 계산해 보다가 위의 방법과 동일하지만 cnt를 1씩 증가해주고 나중에 cnt만큼 곱하고 또 뭐를 빼고 이런 번거로운 일을 하지 않고 그때 그때 현재 참조하고 있는 값과 비교하는 값의 차이를 answer에 더해주면 되겠다! 라는 생각이 떠올라서 최종 코드가 완성 되었다.

1. 매매가를 담은 배열 salePrices를 뒤에서부터 접근한다.
2. 현재 접근한 인덱스에서 한 칸씩 앞으로 이동하며 비교할 때, 앞에 있는 인덱스의 값들 중 현재 값보다 더 낮은 값이 있다면 (현재 값-앞에 있는 값)을 해서 answer에 더해준다. 현재 값보다 더 큰 값이 나오면 멈추고, 거기를 현재 값으로 업데이트 한다.
3. 앞에 값들이 남아있다면 2번을 반복한다