문제

예제입력1에 대한 문제풀이

입력

4 6
a t c i s w

모음 : a i
자음 : t c s w
위의 자모음 각각을 오름차순 정렬하면 아래와 같다.
모음 : a i
자음 : c s t w

암호의 조건인 모음 1개 이상, 자음 2개 이상을 만족하는 암호를 바로 만들기보단 입력된 총 6개의 알파벳으로 가능한 모든 암호 조합을 만들고 조건에 해당하는 경우만 출력한다. 가능한 모든 암호 조합은 아래와 같다.

4 6
a t c i s w
a c i s t w
a
ac
aci
acis
acist
acistw
acisw
acit
acitw
aciw
acs
acst
acstw
acsw
act
actw
acw
ai
ais
aist
aistw
aisw
ait
aitw
aiw
as
ast
astw
asw
at
atw
aw
c
ci
cis
cist
cistw
cisw
cit
citw
ciw
cs
cst
cstw
csw
ct
ctw
cw
i
is
ist
istw
isw
it
itw
iw
s
st
stw
sw
t
tw
w

코드

```cpp #define _CRT_SECURE_NO_WARNINGS #include #include #include #include using namespace std;

문제

문제풀이

(A+B) + (A+B+C) + (A+B+C+D) + …로 생각하여 가장 작은 숫자가 가장 많이 더해지도록 구현할 수 있지만 이는 틀린 방법이다. 예를 들어 5 6 7 8의 경우, 위와 같은 방식으로 해를 구하면 55가 나오지만 실제 답은 52이다. (5+6)+(7+8)+(11+15)=11+15+26=52로 계산된다.
우선순위 큐를 하나 만들고 입력값들을 큐에 집어넣되, 가장 작은 두 개의 값은 서로 더한 후에 집어넣는다. 예를 들어, s=[5 6 7 8]이면, q=[11 7 8]이 되는 것. 이 상태에서 한번 더 정렬해서 가장 작은 두 수 를 찾고 서로 더한 후에 집어 넣는 것을 반복한다. q=[11 15]가 되며 이 과정에서 answer에 더해진 결과물을 저장해두었다가 계속해서 갱신한다. 즉, answer = (5+6) + (7+8) + (11+15) = 52가 된다.

코드

```cpp #define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std;

Link

문제

문제풀이

행과 열의 크기를 입력받아 board에 r x c의 형태로 값을 저장한다. 시작 위치는 (0,0)으로 고정이고, 그 위치에 있는 알파벳을 방문 체크한다. check_board에 지나온 알파벳을 하나씩 넣기보다, A~Z 크기의 체크보드 bool형으로 만들고 방문시 true, 미방문시 false를 입력하는 방식이다. 처음으로 돌아와서, ‘A’를 빼주면 해당 알파벳이 ‘A’로부터 얼마나 떨어졌는지 알 수 있으므로 ‘A’뺀 숫자를 위치로 삼고(char A=65, B=66, C=67 ..이므로 A=0,B=1,C=2..로 바꾼 셈) 그 위치의 알파벳을 방문 체크(true)해주고 dfs시작한다.

시작 위치를 1로 카운트하면서 그 위치의 주변을 살펴 갈 수 있는 곳을 탐색한다. 다음 위치에 있는 알파벳이 방문한 적 없는 곳이면 해당 위치로 이동하면서 체크보드에 체크하고 그 위치부터 다시 dfs를 호출한다. 이때, dfs를 호출하는 횟수를 카운트하면 몇 칸 이동하는지 알 수 있다. 중요한 것은, dfs호출 후에, 그 위치의 체크보드를 비워주어야 한다는 것이다. 이는, 왼,오,위,아 네 개의 후보군을 탐색할 때, 왼쪽에 ‘F’가 있다고 해도 이와는 별개로 오른쪽에 있는 ‘F’에도 갈 수 있음을 의미한다.

코드

```cpp #include #include #include using namespace std;