More actions
imported>Unknown No edit summary |
(Table transclusion repair v1) |
||
| Line 4: | Line 4: | ||
=== About [[EditStepLadders]] === | === About [[EditStepLadders]] === | ||
편집 단계(edit step)란 어떤 단어 x에서 다른 단어 y로의 변환을 뜻하는데, 이때 x와 y는 어떤 사전에 있는 단어며 한 글자를 추가하거나 삭제하거나 바꿈으로써 x를 y로 변환할 수 있어야 한다. 예를 들어 dig에서 dog로, 또는 dog에서 do로 변환하는 것은 모두 편집 단계라고 할 수 있다. 편집 단계 사다리(edit step ladder)란 사전 순서대로 정렬된 w | 편집 단계(edit step)란 어떤 단어 x에서 다른 단어 y로의 변환을 뜻하는데, 이때 x와 y는 어떤 사전에 있는 단어며 한 글자를 추가하거나 삭제하거나 바꿈으로써 x를 y로 변환할 수 있어야 한다. 예를 들어 dig에서 dog로, 또는 dog에서 do로 변환하는 것은 모두 편집 단계라고 할 수 있다. 편집 단계 사다리(edit step ladder)란 사전 순서대로 정렬된 w<sub>1</sub>,w<sub>2</sub>,...,w<sub>n</sub>이라는 단어들을 뜻하는데, 이때 1에서 n-1까지의 모든 i에 대해 w<sub>i</sub>에서 w<sub>i+1</sub>로 넘어가는 변환은 편집 단계여야 한다. | ||
어떤 사전이 주어졌을 때 편집 단계 사다리의 최대 길이를 계산하는 문제를 풀어보자. | 어떤 사전이 주어졌을 때 편집 단계 사다리의 최대 길이를 계산하는 문제를 풀어보자. | ||
| Line 15: | Line 15: | ||
=== Sample Input === | === Sample Input === | ||
cat | |||
dig | dig | ||
dog | dog | ||
| Line 23: | Line 23: | ||
fog | fog | ||
log | log | ||
wine | wine | ||
=== Sample Output === | === Sample Output === | ||
5 | |||
=== 풀이 === | === 풀이 === | ||
{| class="wikitable" | {| class="wikitable" style="width:100%;" | ||
|- | |- | ||
| 작성자 | | 작성자 | ||
| Line 50: | Line 50: | ||
---- | ---- | ||
[[문제분류]] [[경시대회준비반]] | [[문제분류]] [[경시대회준비반]] | ||
Latest revision as of 12:46, 27 March 2026
인기도:B(A,B,C), 성공률:낮음(낮음,보통,높음), 레벨:3(1~4)
About EditStepLadders
편집 단계(edit step)란 어떤 단어 x에서 다른 단어 y로의 변환을 뜻하는데, 이때 x와 y는 어떤 사전에 있는 단어며 한 글자를 추가하거나 삭제하거나 바꿈으로써 x를 y로 변환할 수 있어야 한다. 예를 들어 dig에서 dog로, 또는 dog에서 do로 변환하는 것은 모두 편집 단계라고 할 수 있다. 편집 단계 사다리(edit step ladder)란 사전 순서대로 정렬된 w1,w2,...,wn이라는 단어들을 뜻하는데, 이때 1에서 n-1까지의 모든 i에 대해 wi에서 wi+1로 넘어가는 변환은 편집 단계여야 한다.
어떤 사전이 주어졌을 때 편집 단계 사다리의 최대 길이를 계산하는 문제를 풀어보자.
Input
프로그램에 사전이 입력되는데, 소문자로 된 단어들이 한 줄에 하나씩 사전 순서대로 입력된다. 어떤 단어도 16글자를 넘어가면 안 되며, 사전에 들어갈 수 있는 단어의 개수는 최대 25,000개다.
Output
가장 긴 편집 단계 사다리에 들어있는 단어의 개수를 나타내는 정수 한 개를 출력한다.
Sample Input
cat
dig dog fig fin fine fog log wine
Sample Output
5
풀이
| 작성자 | 사용언어 | 개발시간 | 코드 |
| 황재선 | Java | . | EditStepLadders/황재선 |
| 조현태 | C++ | . | EditStepLadders/조현태 |