<div> <div class="col-md-12" style="padding-right:15px;padding-left:15px;float:left;width:1170px;color:#333333;font-family:'Open Sans', 'Helvetica Neue', Helvetica, Arial, 'Apple SD Gothic Neo', 'Noto Sans CJK KR', 'Noto Sans KR', '나눔바른고딕', '나눔고딕', NanumGothic, '맑은고딕', 'Malgun Gothic', 'Nanum Gothic', sans-serif;font-size:13px;"><section><div class="headline" style="margin:10px 0px 25px;border-bottom:1px dotted rgb(228,233,240);"> <h2 style="font-weight:normal;line-height:33px;color:#585f69;margin:0px 0px -2px;font-size:22px;padding-bottom:5px;display:inline-block;border-bottom:2px solid rgb(0,118,192);">문제</h2></div> <div style="font-size:medium;line-height:30px;"> <p style="margin:0px 0px 10px;color:#555555;">문자열과 놀기를 세상에서 제일 좋아하는 영식이는 오늘도 문자열 2개의 LCS(Longest Common Subsequence)를 구하고 있었다. 어느 날 영식이는 조교들이 문자열 3개의 LCS를 구하는 것을 보았다. 영식이도 도전해 보았지만 실패하고 말았다.</p> <p style="margin:0px 0px 10px;color:#555555;">이제 우리가 할 일은 다음과 같다. 영식이를 도와서 문자열 3개의 LCS를 구하는 프로그램을 작성하라.</p></div></section></div> <div class="col-md-12" style="padding-right:15px;padding-left:15px;float:left;width:1170px;color:#333333;font-family:'Open Sans', 'Helvetica Neue', Helvetica, Arial, 'Apple SD Gothic Neo', 'Noto Sans CJK KR', 'Noto Sans KR', '나눔바른고딕', '나눔고딕', NanumGothic, '맑은고딕', 'Malgun Gothic', 'Nanum Gothic', sans-serif;font-size:13px;"><section><div class="headline" style="margin:10px 0px 25px;border-bottom:1px dotted rgb(228,233,240);"> <h2 style="font-weight:normal;line-height:33px;color:#585f69;margin:0px 0px -2px;font-size:22px;padding-bottom:5px;display:inline-block;border-bottom:2px solid rgb(0,118,192);">입력</h2></div> <div style="font-size:medium;line-height:30px;"> <p style="margin:0px 0px 10px;color:#555555;">첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. (각 문자열의 길이는 100보다 작거나 같다)</p></div></section></div> <div class="col-md-12" style="padding-right:15px;padding-left:15px;float:left;width:1170px;color:#333333;font-family:'Open Sans', 'Helvetica Neue', Helvetica, Arial, 'Apple SD Gothic Neo', 'Noto Sans CJK KR', 'Noto Sans KR', '나눔바른고딕', '나눔고딕', NanumGothic, '맑은고딕', 'Malgun Gothic', 'Nanum Gothic', sans-serif;font-size:13px;"><section><div class="headline" style="margin:10px 0px 25px;border-bottom:1px dotted rgb(228,233,240);"> <h2 style="font-weight:normal;line-height:33px;color:#585f69;margin:0px 0px -2px;font-size:22px;padding-bottom:5px;display:inline-block;border-bottom:2px solid rgb(0,118,192);">출력</h2></div> <div style="font-size:medium;line-height:30px;"> <p style="margin:0px 0px 10px;color:#555555;">첫 줄에 첫 번째 문자열과 두 번째 문자열과 세 번째 문자열의 LCS의 길이를 출력한다.</p> <p style="margin:0px 0px 10px;color:#555555;"><br></p></div></section></div></div> <div><br></div> <div><br></div> <div><br></div> <div>제 소스</div> <div> <div class="colorscripter-code" style="color:#010101;overflow:auto;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> <table class="colorscripter-code-table" style="margin:0px;padding:0px;border:none;background-color:#fafafa;" cellspacing="0" cellpadding="0"><tbody><tr><td style="padding:6px;border-right:2px solid rgb(229,229,229);"> <div style="margin:0px;padding:0px;text-align:right;color:#666666;line-height:130%;"> <div style="line-height:130%;">1</div> <div style="line-height:130%;">2</div> <div style="line-height:130%;">3</div> <div style="line-height:130%;">4</div> <div style="line-height:130%;">5</div> <div style="line-height:130%;">6</div> <div style="line-height:130%;">7</div> <div style="line-height:130%;">8</div> <div style="line-height:130%;">9</div> <div style="line-height:130%;">10</div> <div style="line-height:130%;">11</div> <div style="line-height:130%;">12</div> <div style="line-height:130%;">13</div> <div style="line-height:130%;">14</div> <div style="line-height:130%;">15</div> <div style="line-height:130%;">16</div> <div style="line-height:130%;">17</div> <div style="line-height:130%;">18</div> <div style="line-height:130%;">19</div> <div style="line-height:130%;">20</div> <div style="line-height:130%;">21</div> <div style="line-height:130%;">22</div> <div style="line-height:130%;">23</div> <div style="line-height:130%;">24</div> <div style="line-height:130%;">25</div> <div style="line-height:130%;">26</div> <div style="line-height:130%;">27</div> <div style="line-height:130%;">28</div> <div style="line-height:130%;">29</div> <div style="line-height:130%;">30</div> <div style="line-height:130%;">31</div> <div style="line-height:130%;">32</div> <div style="line-height:130%;">33</div> <div style="line-height:130%;">34</div> <div style="line-height:130%;">35</div> <div style="line-height:130%;">36</div> <div style="line-height:130%;">37</div> <div style="line-height:130%;">38</div> <div style="line-height:130%;">39</div> <div style="line-height:130%;">40</div> <div style="line-height:130%;">41</div> <div style="line-height:130%;">42</div> <div style="line-height:130%;">43</div> <div style="line-height:130%;">44</div> <div style="line-height:130%;">45</div> <div style="line-height:130%;">46</div> <div style="line-height:130%;">47</div> <div style="line-height:130%;">48</div> <div style="line-height:130%;">49</div> <div style="line-height:130%;">50</div> <div style="line-height:130%;">51</div> <div style="line-height:130%;">52</div> <div style="line-height:130%;">53</div> <div style="line-height:130%;">54</div> <div style="line-height:130%;">55</div> <div style="line-height:130%;">56</div> <div style="line-height:130%;">57</div> <div style="line-height:130%;">58</div> <div style="line-height:130%;">59</div> <div style="line-height:130%;">60</div> <div style="line-height:130%;">61</div> <div style="line-height:130%;">62</div> <div style="line-height:130%;">63</div> <div style="line-height:130%;">64</div> <div style="line-height:130%;">65</div> <div style="line-height:130%;">66</div> <div style="line-height:130%;">67</div> <div style="line-height:130%;">68</div> <div style="line-height:130%;">69</div></div></td> <td style="padding:6px 0px;"> <div style="margin:0px;padding:0px;color:#010101;line-height:130%;"> <div style="padding:0px 6px;white-space:pre;line-height:130%;"><span style="color:#0086b3;">#include</span> <span style="color:#ff3399;"></span><span style="color:#a71d5d;"><</span>stdio.h<span style="color:#ff3399;"></span><span style="color:#a71d5d;">></span></div> <div style="padding:0px 6px;white-space:pre;line-height:130%;"><span style="color:#0086b3;">#include</span> <span style="color:#ff3399;"></span><span style="color:#a71d5d;"><</span>stdlib.h<span style="color:#ff3399;"></span><span style="color:#a71d5d;">></span></div> <div style="padding:0px 6px;white-space:pre;line-height:130%;"><span style="color:#0086b3;">#include</span> <span style="color:#ff3399;"></span><span style="color:#a71d5d;"><</span><span style="color:#066de2;">string</span>.h<span style="color:#ff3399;"></span><span style="color:#a71d5d;">></span></div> <div style="padding:0px 6px;white-space:pre;line-height:130%;"> </div> <div style="padding:0px 6px;white-space:pre;line-height:130%;"><span style="color:#0086b3;">#define</span> INPUT_COUNT <span style="color:#0099cc;">3</span></div> <div style="padding:0px 6px;white-space:pre;line-height:130%;"> </div> <div style="padding:0px 6px;white-space:pre;line-height:130%;"><span style="color:#a71d5d;">void</span> inputString(<span style="color:#066de2;">char</span> <span style="color:#ff3399;"></span><span style="color:#a71d5d;">*</span><span style="color:#ff3399;"></span><span style="color:#a71d5d;">*</span>str);</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;"><span style="color:#066de2;">int</span> find3CS(<span style="color:#066de2;">char</span> <span style="color:#ff3399;"></span><span style="color:#a71d5d;">*</span><span style="color:#ff3399;"></span><span style="color:#a71d5d;">*</span>str, <span style="color:#066de2;">int</span> seq1, <span style="color:#066de2;">int</span> seq2, <span style="color:#066de2;">int</span> seq3);</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;"><span style="color:#a71d5d;">void</span> sortString(<span style="color:#066de2;">char</span> <span style="color:#ff3399;"></span><span style="color:#a71d5d;">*</span><span style="color:#ff3399;"></span><span style="color:#a71d5d;">*</span>str);</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;"> </div> <div style="padding:0px 6px;white-space:pre;line-height:130%;"><span style="color:#066de2;">int</span> main()</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">{</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">    <span style="color:#066de2;">int</span> i, lcs <span style="color:#ff3399;"></span><span style="color:#a71d5d;">=</span> <span style="color:#0099cc;">0</span>;</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">    <span style="color:#066de2;">char</span> <span style="color:#ff3399;"></span><span style="color:#a71d5d;">*</span>str[INPUT_COUNT];</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">    inputString(str);</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">    <span style="color:#a71d5d;">for</span> (i <span style="color:#ff3399;"></span><span style="color:#a71d5d;">=</span> <span style="color:#0099cc;">0</span>; i <span style="color:#ff3399;"></span><span style="color:#a71d5d;"><</span> strlen(str[<span style="color:#0099cc;">0</span>]); i<span style="color:#ff3399;"></span><span style="color:#a71d5d;">+</span><span style="color:#ff3399;"></span><span style="color:#a71d5d;">+</span>) {</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">        <span style="color:#066de2;">int</span> ccs;</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">        ccs <span style="color:#ff3399;"></span><span style="color:#a71d5d;">=</span> find3CS(str, i, <span style="color:#0099cc;">0</span>, <span style="color:#0099cc;">0</span>);</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">        <span style="color:#a71d5d;">if</span> (lcs <span style="color:#ff3399;"></span><span style="color:#a71d5d;"><</span> ccs)    lcs <span style="color:#ff3399;"></span><span style="color:#a71d5d;">=</span> ccs;</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">    }</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">    <span style="color:#066de2;">printf</span>(<span style="color:#63a35c;">"%d"</span>, lcs);</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">    <span style="color:#a71d5d;">for</span> (i <span style="color:#ff3399;"></span><span style="color:#a71d5d;">=</span> <span style="color:#0099cc;">0</span>; i <span style="color:#ff3399;"></span><span style="color:#a71d5d;"><</span> INPUT_COUNT; i<span style="color:#ff3399;"></span><span style="color:#a71d5d;">+</span><span style="color:#ff3399;"></span><span style="color:#a71d5d;">+</span>)    <span style="color:#066de2;">free</span>(str[i]);</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">}</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;"> </div> <div style="padding:0px 6px;white-space:pre;line-height:130%;"><span style="color:#999999;">//문자열을 입력받아 동적할당해줌.</span></div> <div style="padding:0px 6px;white-space:pre;line-height:130%;"><span style="color:#a71d5d;">void</span> inputString(<span style="color:#066de2;">char</span> <span style="color:#ff3399;"></span><span style="color:#a71d5d;">*</span><span style="color:#ff3399;"></span><span style="color:#a71d5d;">*</span>str)</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">{</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">    <span style="color:#066de2;">int</span> i;</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">    <span style="color:#066de2;">char</span> buffer[BUFSIZ];</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">    <span style="color:#a71d5d;">for</span> (i <span style="color:#ff3399;"></span><span style="color:#a71d5d;">=</span> <span style="color:#0099cc;">0</span>; i <span style="color:#ff3399;"></span><span style="color:#a71d5d;"><</span> INPUT_COUNT; i<span style="color:#ff3399;"></span><span style="color:#a71d5d;">+</span><span style="color:#ff3399;"></span><span style="color:#a71d5d;">+</span>) {</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">        <span style="color:#066de2;">scanf</span>(<span style="color:#63a35c;">"%s"</span>, buffer);</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">        str[i] <span style="color:#ff3399;"></span><span style="color:#a71d5d;">=</span> (<span style="color:#066de2;">char</span><span style="color:#a71d5d;">*</span>)<span style="color:#066de2;">malloc</span>(strlen(buffer)<span style="color:#ff3399;"></span><span style="color:#a71d5d;">+</span><span style="color:#0099cc;">1</span>);</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">        memcpy(str[i], buffer, strlen(buffer) <span style="color:#ff3399;"></span><span style="color:#a71d5d;">+</span> <span style="color:#0099cc;">1</span>);</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">    }</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">}</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;"> </div> <div style="padding:0px 6px;white-space:pre;line-height:130%;"><span style="color:#999999;">//CS(commom sequence) 찾기 함수</span></div> <div style="padding:0px 6px;white-space:pre;line-height:130%;"><span style="color:#066de2;">int</span> find3CS(<span style="color:#066de2;">char</span> <span style="color:#ff3399;"></span><span style="color:#a71d5d;">*</span><span style="color:#ff3399;"></span><span style="color:#a71d5d;">*</span>str, <span style="color:#066de2;">int</span> seq1, <span style="color:#066de2;">int</span> seq2, <span style="color:#066de2;">int</span> seq3)</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">{</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">    <span style="color:#066de2;">int</span> i, j, k;</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">    <span style="color:#066de2;">char</span> cmpchar;</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">    sortString(str);</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">    <span style="color:#a71d5d;">for</span> (i <span style="color:#ff3399;"></span><span style="color:#a71d5d;">=</span> seq1; i <span style="color:#ff3399;"></span><span style="color:#a71d5d;"><</span> strlen(str[<span style="color:#0099cc;">0</span>]); i<span style="color:#ff3399;"></span><span style="color:#a71d5d;">+</span><span style="color:#ff3399;"></span><span style="color:#a71d5d;">+</span>) {</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">        cmpchar <span style="color:#ff3399;"></span><span style="color:#a71d5d;">=</span> str[<span style="color:#0099cc;">0</span>][i];</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">        <span style="color:#a71d5d;">for</span> (j <span style="color:#ff3399;"></span><span style="color:#a71d5d;">=</span> seq2; j <span style="color:#ff3399;"></span><span style="color:#a71d5d;"><</span> strlen(str[<span style="color:#0099cc;">1</span>]); j<span style="color:#ff3399;"></span><span style="color:#a71d5d;">+</span><span style="color:#ff3399;"></span><span style="color:#a71d5d;">+</span>) {</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">            <span style="color:#a71d5d;">if</span> (cmpchar <span style="color:#ff3399;"></span><span style="color:#a71d5d;">=</span><span style="color:#ff3399;"></span><span style="color:#a71d5d;">=</span> str[<span style="color:#0099cc;">1</span>][j]) {</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">                <span style="color:#a71d5d;">for</span>(k <span style="color:#ff3399;"></span><span style="color:#a71d5d;">=</span> seq3; k <span style="color:#ff3399;"></span><span style="color:#a71d5d;"><</span> strlen(str[<span style="color:#0099cc;">2</span>]); k<span style="color:#ff3399;"></span><span style="color:#a71d5d;">+</span><span style="color:#ff3399;"></span><span style="color:#a71d5d;">+</span>)</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">                    <span style="color:#a71d5d;">return</span> find3CS(str, i <span style="color:#ff3399;"></span><span style="color:#a71d5d;">+</span> <span style="color:#0099cc;">1</span>, j <span style="color:#ff3399;"></span><span style="color:#a71d5d;">+</span> <span style="color:#0099cc;">1</span>, k <span style="color:#ff3399;"></span><span style="color:#a71d5d;">+</span> <span style="color:#0099cc;">1</span>) <span style="color:#ff3399;"></span><span style="color:#a71d5d;">+</span> <span style="color:#0099cc;">1</span>;</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">            }</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">        }</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">    }</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">    <span style="color:#a71d5d;">return</span> <span style="color:#0099cc;">0</span>;</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">}</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;"> </div> <div style="padding:0px 6px;white-space:pre;line-height:130%;"><span style="color:#999999;">//문자열의 길이기준으로 오름차순 정렬</span></div> <div style="padding:0px 6px;white-space:pre;line-height:130%;"><span style="color:#a71d5d;">void</span> sortString(<span style="color:#066de2;">char</span> <span style="color:#ff3399;"></span><span style="color:#a71d5d;">*</span><span style="color:#ff3399;"></span><span style="color:#a71d5d;">*</span>str)</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">{</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">    <span style="color:#066de2;">int</span> i, j, len;</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">    <span style="color:#066de2;">char</span> <span style="color:#ff3399;"></span><span style="color:#a71d5d;">*</span>tmp;</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">    <span style="color:#a71d5d;">for</span> (i <span style="color:#ff3399;"></span><span style="color:#a71d5d;">=</span> <span style="color:#0099cc;">0</span>; i <span style="color:#ff3399;"></span><span style="color:#a71d5d;"><</span> INPUT_COUNT; i<span style="color:#ff3399;"></span><span style="color:#a71d5d;">+</span><span style="color:#ff3399;"></span><span style="color:#a71d5d;">+</span>) {</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">        <span style="color:#a71d5d;">for</span> (j <span style="color:#ff3399;"></span><span style="color:#a71d5d;">=</span> <span style="color:#0099cc;">1</span>; j <span style="color:#ff3399;"></span><span style="color:#a71d5d;"><</span> INPUT_COUNT; j<span style="color:#ff3399;"></span><span style="color:#a71d5d;">+</span><span style="color:#ff3399;"></span><span style="color:#a71d5d;">+</span>) {</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">            <span style="color:#a71d5d;">if</span> (strlen(str[i]) <span style="color:#ff3399;"></span><span style="color:#a71d5d;">></span> strlen(str[j])) {</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">                tmp <span style="color:#ff3399;"></span><span style="color:#a71d5d;">=</span> str[i];</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">                str[i] <span style="color:#ff3399;"></span><span style="color:#a71d5d;">=</span> str[j];</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">                str[j] <span style="color:#ff3399;"></span><span style="color:#a71d5d;">=</span> tmp;</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">            }</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">        }</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">    }</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">}</div></div> <div style="text-align:right;margin-top:-13px;margin-right:5px;font-size:9px;font-style:italic;"><a target="_blank" href="http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5;">Colored by Color Scripter</a></div></td> <td style="vertical-align:bottom;padding:0px 2px 4px 0px;"><a target="_blank" href="http://colorscripter.com/info#e" target="_blank" style="color:#FFFFFF;"><span style="font-size:9px;background-color:#e5e5e5;padding:1px;">cs</span></a></td></tr></tbody></table><br></div></div> <div class="colorscripter-code" style="color:#010101;overflow:auto;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">제가 직접 실행시켜봤을 때는 문제가 없었는데, 자꾸 제출만 하면 틀렸다고 합니다. 혹시 소스에 문제점이 보이시나요?</div> <div class="colorscripter-code" style="color:#010101;overflow:auto;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">(혹시몰라 띄어쓰기도 입력받으려고 scanf대신 gets를 써봤으나 안되네요)</div>