-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path230317.html
More file actions
90 lines (88 loc) · 14.2 KB
/
230317.html
File metadata and controls
90 lines (88 loc) · 14.2 KB
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
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>1106번 - 호텔</title>
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/highlight.js/11.7.0/styles/default.min.css">
<link href="https://cdn.jsdelivr.net/npm/bootstrap@5.3.0-alpha1/dist/css/bootstrap.min.css" rel="stylesheet" integrity="sha384-GLhlTQ8iRABdZLl6O3oVMWSktQOp6b7In1Zl3/Jr59b6EGGoI1aFkw7cmDA6j6gD" crossorigin="anonymous">
<script src="https://cdn.jsdelivr.net/npm/bootstrap@5.3.0-alpha1/dist/js/bootstrap.bundle.min.js" integrity="sha384-w76AqPfDkMBDXo30jS1Sgez6pr3x5MlQ1ZAGC+nuZB+EYdgRZgiwxhTBTkF7CXvN" crossorigin="anonymous"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/highlight.js/11.7.0/highlight.min.js"></script>
<link href="./static/css/main.css" rel="stylesheet">
</head>
<body>
<div class="md-container">
<h2 class="fw-bold">1106번 - 호텔</h2>
<h4 id="-">분류 : 다이나믹 프로그래밍, 배낭 문제</h4>
<h4 id="-">제약조건</h4>
<ul>
<li><p>도시를 홍보하는 데 드는 비용과 유치할 수 있는 고객 양이 정해진다. 무한히 재사용이 가능하다.</p>
</li>
<li><p>목표하는 고객 수치가 있으나 그 수치를 넘어가도 괜찮다. 딱 맞출 필요가 없다.</p>
</li>
</ul>
<h4 id="-">설계</h4>
<ol>
<li><p>처음에는 그리디로 풀이를 시도 했다. 무조건 가장 효율이 좋은 애로만 다 채우고 남은 부분이 있다면 그 다음 효율 좋은 애로 채우는 식을 생각했다.</p>
</li>
<li><p>위의 방법은 하지만 반례가 있다 넘어가도 상관이 없기 때문에 넘어간 상태로 제일 효율 좋은 애로 다 채우는 것이 가장 좋은 방법이 될 수도 있다.</p>
</li>
<li><p>그 다음 생각한 방법은 bfs를 통한 모든 경우의 수 탐색이다. N의 개수는 최대 20개다. 그렇다면 bfs로 탐색할 때 한 노드에서 최대 20갈래로 뻗어나간다는 거다. 고객 수 또한 최대 1000임으로 1000을 넘으면 멈춘다고 해도 너무 많은 수다.</p>
</li>
<li><p>마지막으로 고려한 게 dp를 이용해서 모든 경우의 수를 따져도 효율적으로 진행하는 것을 생각했다.</p>
</li>
<li><p>for 문을 이용해서 고객 수 크기 만큼 순회하면서 해당 위치에서의 dp 값을 이용해 그 다음에 갈 수 있는 위치의 dp값을 갱신시키는 방식으로 설계하였다.</p>
<p>(물론 이 방법 외에도 bfs를 이용하지만 dp를 이용해서 도착점의 dp값이 현재 value보다 낮으면 queue에 append 하지 않는 방식으로도 풀릴 것 같지만 시도해보진 않았다.)</p>
</li>
</ol>
<div class="sourceCode" id="cb1"><pre
class="sourceCode java"><code class="sourceCode java"><span id="cb1-1"><a href="#cb1-1" aria-hidden="true" tabindex="-1"></a><span class="kw">import</span> <span class="im">java</span><span class="op">.</span><span class="im">io</span><span class="op">.</span><span class="im">BufferedReader</span><span class="op">;</span></span>
<span id="cb1-2"><a href="#cb1-2" aria-hidden="true" tabindex="-1"></a><span class="kw">import</span> <span class="im">java</span><span class="op">.</span><span class="im">io</span><span class="op">.</span><span class="im">IOException</span><span class="op">;</span></span>
<span id="cb1-3"><a href="#cb1-3" aria-hidden="true" tabindex="-1"></a><span class="kw">import</span> <span class="im">java</span><span class="op">.</span><span class="im">io</span><span class="op">.</span><span class="im">InputStreamReader</span><span class="op">;</span></span>
<span id="cb1-4"><a href="#cb1-4" aria-hidden="true" tabindex="-1"></a><span class="kw">import</span> <span class="im">java</span><span class="op">.</span><span class="im">util</span><span class="op">.</span><span class="im">Arrays</span><span class="op">;</span></span>
<span id="cb1-5"><a href="#cb1-5" aria-hidden="true" tabindex="-1"></a><span class="kw">import</span> <span class="im">java</span><span class="op">.</span><span class="im">util</span><span class="op">.</span><span class="im">HashMap</span><span class="op">;</span></span>
<span id="cb1-6"><a href="#cb1-6" aria-hidden="true" tabindex="-1"></a><span class="kw">import</span> <span class="im">java</span><span class="op">.</span><span class="im">util</span><span class="op">.</span><span class="im">Map</span><span class="op">;</span></span>
<span id="cb1-7"><a href="#cb1-7" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb1-8"><a href="#cb1-8" aria-hidden="true" tabindex="-1"></a><span class="kw">public</span> <span class="kw">class</span> Main <span class="op">{</span></span>
<span id="cb1-9"><a href="#cb1-9" aria-hidden="true" tabindex="-1"></a> <span class="dt">static</span> <span class="dt">int</span> c<span class="op">,</span>n<span class="op">;</span></span>
<span id="cb1-10"><a href="#cb1-10" aria-hidden="true" tabindex="-1"></a> <span class="dt">static</span> <span class="bu">Map</span><span class="op"><</span><span class="bu">Integer</span><span class="op">,</span><span class="bu">Integer</span><span class="op">></span> advertiseCostMap<span class="op">;</span></span>
<span id="cb1-11"><a href="#cb1-11" aria-hidden="true" tabindex="-1"></a> <span class="dt">static</span> <span class="dt">int</span><span class="op">[]</span> dp<span class="op">;</span></span>
<span id="cb1-12"><a href="#cb1-12" aria-hidden="true" tabindex="-1"></a> <span class="dt">static</span> <span class="dt">int</span> res <span class="op">=</span> <span class="op">(</span><span class="dt">int</span><span class="op">)</span><span class="fl">1e9</span><span class="op">;</span></span>
<span id="cb1-13"><a href="#cb1-13" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb1-14"><a href="#cb1-14" aria-hidden="true" tabindex="-1"></a> <span class="kw">public</span> <span class="dt">static</span> <span class="dt">void</span> <span class="fu">main</span><span class="op">(</span><span class="bu">String</span><span class="op">[]</span> args<span class="op">)</span> <span class="kw">throws</span> <span class="bu">IOException</span> <span class="op">{</span></span>
<span id="cb1-15"><a href="#cb1-15" aria-hidden="true" tabindex="-1"></a> <span class="bu">BufferedReader</span> bf <span class="op">=</span> <span class="kw">new</span> <span class="bu">BufferedReader</span><span class="op">(</span><span class="kw">new</span> <span class="bu">InputStreamReader</span><span class="op">(</span><span class="bu">System</span><span class="op">.</span><span class="fu">in</span><span class="op">));</span></span>
<span id="cb1-16"><a href="#cb1-16" aria-hidden="true" tabindex="-1"></a> <span class="bu">String</span><span class="op">[]</span> tmp <span class="op">=</span> bf<span class="op">.</span><span class="fu">readLine</span><span class="op">().</span><span class="fu">split</span><span class="op">(</span><span class="st">" "</span><span class="op">);</span></span>
<span id="cb1-17"><a href="#cb1-17" aria-hidden="true" tabindex="-1"></a> c <span class="op">=</span> <span class="bu">Integer</span><span class="op">.</span><span class="fu">parseInt</span><span class="op">(</span>tmp<span class="op">[</span><span class="dv">0</span><span class="op">]);</span></span>
<span id="cb1-18"><a href="#cb1-18" aria-hidden="true" tabindex="-1"></a> n <span class="op">=</span> <span class="bu">Integer</span><span class="op">.</span><span class="fu">parseInt</span><span class="op">(</span>tmp<span class="op">[</span><span class="dv">1</span><span class="op">]);</span></span>
<span id="cb1-19"><a href="#cb1-19" aria-hidden="true" tabindex="-1"></a> advertiseCostMap <span class="op">=</span> <span class="kw">new</span> <span class="bu">HashMap</span><span class="op"><>();</span></span>
<span id="cb1-20"><a href="#cb1-20" aria-hidden="true" tabindex="-1"></a> dp <span class="op">=</span> <span class="kw">new</span> <span class="dt">int</span><span class="op">[</span><span class="dv">1101</span><span class="op">];</span></span>
<span id="cb1-21"><a href="#cb1-21" aria-hidden="true" tabindex="-1"></a> <span class="bu">Arrays</span><span class="op">.</span><span class="fu">fill</span><span class="op">(</span>dp<span class="op">,</span> <span class="op">(</span><span class="dt">int</span><span class="op">)</span> <span class="fl">1e9</span><span class="op">);</span></span>
<span id="cb1-22"><a href="#cb1-22" aria-hidden="true" tabindex="-1"></a> dp<span class="op">[</span><span class="dv">0</span><span class="op">]</span> <span class="op">=</span> <span class="dv">0</span><span class="op">;</span></span>
<span id="cb1-23"><a href="#cb1-23" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb1-24"><a href="#cb1-24" aria-hidden="true" tabindex="-1"></a> <span class="cf">for</span> <span class="op">(</span><span class="dt">int</span> i <span class="op">=</span> <span class="dv">0</span><span class="op">;</span> i <span class="op"><</span> n<span class="op">;</span> i<span class="op">++)</span> <span class="op">{</span></span>
<span id="cb1-25"><a href="#cb1-25" aria-hidden="true" tabindex="-1"></a> tmp <span class="op">=</span> bf<span class="op">.</span><span class="fu">readLine</span><span class="op">().</span><span class="fu">split</span><span class="op">(</span><span class="st">" "</span><span class="op">);</span></span>
<span id="cb1-26"><a href="#cb1-26" aria-hidden="true" tabindex="-1"></a> <span class="dt">int</span> key <span class="op">=</span> <span class="bu">Integer</span><span class="op">.</span><span class="fu">parseInt</span><span class="op">(</span>tmp<span class="op">[</span><span class="dv">0</span><span class="op">]);</span></span>
<span id="cb1-27"><a href="#cb1-27" aria-hidden="true" tabindex="-1"></a> <span class="dt">int</span> value <span class="op">=</span> <span class="bu">Integer</span><span class="op">.</span><span class="fu">parseInt</span><span class="op">(</span>tmp<span class="op">[</span><span class="dv">1</span><span class="op">]);</span></span>
<span id="cb1-28"><a href="#cb1-28" aria-hidden="true" tabindex="-1"></a> <span class="cf">if</span> <span class="op">(</span>advertiseCostMap<span class="op">.</span><span class="fu">containsKey</span><span class="op">(</span>key<span class="op">))</span></span>
<span id="cb1-29"><a href="#cb1-29" aria-hidden="true" tabindex="-1"></a> <span class="cf">if</span> <span class="op">(</span>advertiseCostMap<span class="op">.</span><span class="fu">get</span><span class="op">(</span>key<span class="op">)</span> <span class="op">>=</span> value<span class="op">)</span></span>
<span id="cb1-30"><a href="#cb1-30" aria-hidden="true" tabindex="-1"></a> <span class="cf">continue</span><span class="op">;</span></span>
<span id="cb1-31"><a href="#cb1-31" aria-hidden="true" tabindex="-1"></a> advertiseCostMap<span class="op">.</span><span class="fu">put</span><span class="op">(</span>key<span class="op">,</span>value<span class="op">);</span></span>
<span id="cb1-32"><a href="#cb1-32" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span>
<span id="cb1-33"><a href="#cb1-33" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb1-34"><a href="#cb1-34" aria-hidden="true" tabindex="-1"></a> <span class="cf">for</span> <span class="op">(</span><span class="dt">int</span> i <span class="op">=</span> <span class="dv">0</span><span class="op">;</span> i <span class="op"><</span> c<span class="op">;</span> i<span class="op">++)</span> <span class="op">{</span></span>
<span id="cb1-35"><a href="#cb1-35" aria-hidden="true" tabindex="-1"></a> <span class="cf">for</span> <span class="op">(</span><span class="dt">int</span> key <span class="op">:</span> advertiseCostMap<span class="op">.</span><span class="fu">keySet</span><span class="op">())</span> <span class="op">{</span></span>
<span id="cb1-36"><a href="#cb1-36" aria-hidden="true" tabindex="-1"></a> <span class="dt">int</span> value <span class="op">=</span> advertiseCostMap<span class="op">.</span><span class="fu">get</span><span class="op">(</span>key<span class="op">);</span></span>
<span id="cb1-37"><a href="#cb1-37" aria-hidden="true" tabindex="-1"></a> dp<span class="op">[</span>i<span class="op">+</span>value<span class="op">]</span> <span class="op">=</span> <span class="bu">Math</span><span class="op">.</span><span class="fu">min</span><span class="op">(</span>dp<span class="op">[</span>i<span class="op">+</span>value<span class="op">],</span>dp<span class="op">[</span>i<span class="op">]</span> <span class="op">+</span> key<span class="op">);</span></span>
<span id="cb1-38"><a href="#cb1-38" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span>
<span id="cb1-39"><a href="#cb1-39" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span>
<span id="cb1-40"><a href="#cb1-40" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb1-41"><a href="#cb1-41" aria-hidden="true" tabindex="-1"></a> <span class="cf">for</span> <span class="op">(</span><span class="dt">int</span> i <span class="op">=</span> c<span class="op">;</span> i <span class="op"><</span> <span class="dv">1101</span><span class="op">;</span> i<span class="op">++)</span></span>
<span id="cb1-42"><a href="#cb1-42" aria-hidden="true" tabindex="-1"></a> res <span class="op">=</span> <span class="bu">Math</span><span class="op">.</span><span class="fu">min</span><span class="op">(</span>res<span class="op">,</span>dp<span class="op">[</span>i<span class="op">]);</span></span>
<span id="cb1-43"><a href="#cb1-43" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb1-44"><a href="#cb1-44" aria-hidden="true" tabindex="-1"></a> <span class="bu">System</span><span class="op">.</span><span class="fu">out</span><span class="op">.</span><span class="fu">println</span><span class="op">(</span>res<span class="op">);</span></span>
<span id="cb1-45"><a href="#cb1-45" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span>
<span id="cb1-46"><a href="#cb1-46" aria-hidden="true" tabindex="-1"></a><span class="op">}</span></span></code></pre></div>
</div>
</body>
</html>