프로그래머스 문제
https://school.programmers.co.kr/learn/courses/30/lessons/131129
못 푼 후기
1. 분석
느낌상 DP 문제였지만 방법이 안 떠오르기도 했고 다른 방식으로 풀어보고 싶어서 여러 방법을 사용하기로 했다. 그 결과 7시간 동안 같은 문제만 보는 중.
2. 이진 탐색
첫 시도는 이진 탐색으로 해당 숫자에 대한 최소 루프 수를 구하고,
- (루프) * 50으로 채워보기
- (루프 - 1) * 50 + 나머지 적당히 채워보기
- (루프 - 2) * 50 + 나머지 적당히 채워보기
해서 가장 최적 값이 나오는 걸로 가져오기로 했다. 내 기억으로 히든 테케 3~4개 빼고 다 맞았던 걸로 기억하는데 그 이상으로 도무지 발전할 수 없어서 놓아주기로 했다.
3. BF
무시무시한 BF로 돌려버리기. 당연히 10만이라는 숫자는 BF로 못 돌린다. O(n^2) = 10,000,000,000 이니까, 와! 1000초 안에 해결 가능! 그냥 도대체 뭔 숫자가 나오는지만 좀 알아보자... 라는 느낌으로 구현한 듯.
배열 관리 클래스 하나 만들어두고, target + 1만큼의 배열 안에 값을 비교해서 스코어를 이것저것 넣는 방식이었다.
대충 900까지는 뽑아내 보고 테케 돌렸는데 별로 의미 없어서 텍스트 파일만 뽑아내고 다시 지웠다.
4. 경우의 수
대충 이런 경우 저런 경우를 뽑아내서 비교하는 방식.
- 50 + 가장 큰 숫자로 채우기
- 50 + 20 미만으로 채우기
- 60 + 가장 큰 숫자로 채우기
- 60 + 20 미만을 채우기
- 20 미만으로만 채우기
- 그냥 큰 숫자로 다 채우기
6개 케이스 전부 다 비교해서 값을 뽑아냈는데 틀린 값이 좀 있었다.
85, 2 : 0 / 85, 3 : 3
85는 40 + 45로 [2, 0]이 정답이 맞는데 가장 큰 값으로만 채우다 보니까 이게 불가능한 것 같다.
5. 질문하기 배끼기
밤에 잠 못 잘 것 같아서 그냥 베꼈다. 아무튼, 핵심은 250 이후 구간에 있다.
faul2chris님 감사합니다. (https://school.programmers.co.kr/questions/49069)
250, 5 : 5 310, 6 : 5 370, 7 : 5 430, 8 : 5
251, 5 : 4 311, 6 : 4 371, 7 : 4 431, 8 : 4
252, 5 : 3 312, 6 : 3 372, 7 : 3 432, 8 : 3
253, 5 : 2 313, 6 : 2 373, 7 : 2 433, 8 : 2
254, 5 : 4 314, 6 : 4 374, 7 : 4 434, 8 : 4
255, 5 : 3 315, 6 : 3 375, 7 : 3 435, 8 : 3
256, 5 : 2 316, 6 : 2 376, 7 : 2 436, 8 : 2
257, 5 : 4 317, 6 : 4 377, 7 : 4 437, 8 : 4
258, 5 : 3 318, 6 : 3 378, 7 : 3 438, 8 : 3
259, 5 : 2 319, 6 : 2 379, 7 : 2 439, 8 : 2
260, 5 : 4 320, 6 : 4 380, 7 : 4 440, 8 : 4
250(50점*5번)까지는 60보다 작은 수 50을 모두 사용하는게 좋은 케이스가 나오지만, 그 이후로는 무조건 60이 한개 이상 들어가야 한다. 250 ~ 310 부터는 +60의 무한 반복이라는 뜻. 사실 하라는 대로도 안했다. 귀찮아서 그냥 310까지 BF돌려서 풀었다.
7. 실행 결과
8. 코드
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
public class Solution {
public struct Score
{
public int value;
public int dart;
public int single;
public static Score Max(Score a, Score b)
{
if (a.dart == 0)
{
return b;
}
if (b.dart == 0)
{
return a;
}
if (a.dart < b.dart)
{
return a;
}
if (a.dart > b.dart)
{
return b;
}
if (a.single > b.single)
{
return a;
}
if (a.single < b.single)
{
return b;
}
return a;
}
}
public int[] solution(int target)
{
var bf = new Score[311];
bf[50] = new Score { value = 50, dart = 1, single = 1 };
foreach (var i in Enumerable.Range(1, 20))
{
bf[i * 1] = Score.Max(bf[i * 1], new Score { value = i , dart = 1, single = 1 });
bf[i * 2] = Score.Max(bf[i * 2], new Score { value = i * 2, dart = 1, single = 0 });
bf[i * 3] = Score.Max(bf[i * 3], new Score { value = i * 3, dart = 1, single = 0 });
}
foreach (var scoreA in bf)
{
foreach (var scoreB in bf)
{
if(scoreA.value == 0 || scoreB.value == 0) continue;
var valueSum = scoreA.value + scoreB.value;
if (valueSum < 311)
{
bf[valueSum] = Score.Max(bf[valueSum], new Score { value = valueSum, dart = scoreA.dart + scoreB.dart, single = scoreA.single + scoreB.single });
}
}
}
var answer = new int[] { 0, 0 };
if (310 < target)
{
var quotient = (target - 250) / 60;
var remainder = target - 60 * quotient;
answer[0] += bf[remainder].dart + quotient;
answer[1] += bf[remainder].single;
}
else
{
answer[0] += bf[target].dart;
answer[1] += bf[target].single;
}
return answer;
}
}DP 문제는 얌전히 DP로 풀자는 좋은 교훈을 얻었다.
