Sh4n3e

보드게임 소스 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include int T, N, K, M; int Score[110], UseK[7], Total[7][7][7][7][7][7][7][7]; //Board Score판, 숫자카드 사용내역, DP배열([이전카드][현재카드][1번카드사용내역][2번카드사용내역]...[6번카드사용내역] int Result..

해당 문제는 X일에 각각의 붕어빵 기계가 작동된 날로부터의 Score를 계산하는 문제였다. 해당 문제는 파라메트릭 탐색(Parametric Search)라는 생소한 탐색을 사용함으로써 접근이 쉽지 않았다. 해당코드는 아래에 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93..

파라메트릭 탐색(Parametric Search) 파라메트릭 탐색이란, 이분 탐색(Binary Search)과 비슷한 부류의 탐색이다. 이분 탐색의 경우 어떤 정답을 찾기 위해 탐색을 수행한다. 만약 원하는 정답이 나오지 않는 다면 검색 결과는 없음으로 나오게 된다. 해당 이분 탐색의 예제는 아래와 같다. Address 0 1 2 3 4 5 6 7 Value 1 4 7 24 32 33 42 52 정렬(Sort)되어 있는 상태인 배열에서 우리는 7이라는 값을 찾고 싶다 라고 가정하자. 해당 배열에서의 left주소는 0, right주소는 7이 된다. 해당 값의 mid = (left+right)/2 = 7/2 = 3 이 된다. 그럼 최초에 Martrix[mid]의 값과 우리가 찾고자하는 7과 비교한다. 해당 ..

해당 문제는 Greedy+BFS+Zerosum Problem의 조합을 통해 답을 추출해내는 문제이다. 해당 문제는 농도를 계산하는 문제로 어떻게 효율적으로 제로섬을 만들어낼 것인가에서 고민은 출발하였다. 왜냐하면 입력값의 범위가 20만개였기 때문이었다. 하지만, 입력값의 범위를 0~1000, 즉 1001개로 중복제거를 통해 줄일 수 있었고, BFS를 돌리기 위해 필요한 Cut the Branch 작업이 필요했다. 이 부분은 resultMap라는 1차원 배열을 통해 쉽게 해결할 수 있었다. 다음 아래의 소스는 문제를 해결한 소스코드이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35..