1062 - 가르침

https://www.acmicpc.net/problem/1062

k개의 알파벳을 학습하여 N개의 남극언어 중 몇 개를 읽을 수 있는가인데, 시간 복잡도 계산 안하고 그냥 재귀로 돌려봤다 (패기..!)

매번 모든 알파벳을 검사하기는 힘들다. 그리고 어차피 알파벳은 한번만 배우면 계속 쓰일 수 있다. 그럼 각 단어마다 알파벳의 존재여부를 체크하여 저장할 수가 있는데, 한 단어에서 x번째 알파벳이 사용되었다/안되었다(0/1) 로 구분하면 26자리 2진수 (최대 $2^{26}-1$) 로 표현할 수 있다. 그럼 ACE 는 0 00000 00000 00000 00000 10101 로 표현된다.
소스는 1번째...26번째로 해서 비트가 왼쪽으로 하나씩 밀려있다.

A~Z 중에 k개를 선택했을 때 읽을 수 있는 최대 단어의 갯수를 반환하면서, 그 최대값을 갱신하도록 했다.

그리고 "K개의 글자"에 남극언어에 들어가는 ANTA,TICA 도 포함되어야 한다. (이것때문에 한참 틀렸다) 즉, 5개의 글자(ANTIC)를 반드시 배워야한다는 것이다.

1005 - ACM Craft

DFS로 탐색을 했다. 그냥 DFS를 했다고 해야하나? 역전 앞

노드와 간선의 정보가 주어지고 노드 번호가 주어지면 "그 노드까지 이어진 최장 경로"를 찾는 문제로 생각할 수 있는 데, 그림의 간선 방향을 반대로 바꾸면 "시작노드가 주어지고 시작노드로부터 가장 긴 경로"를 찾는 문제가 될 거라고 생각했다.

하지만 위 알고리즘은 시간초과를 벗어날 수 없게되었다...

친구의 도움을 받아 백트래킹을 이용하면 풀 수 있다는 것을 알게 되었다.
한 노드를 잡고 그 노드까지 가는 최대 경로를 누적하면 목적지까지 가는 노드를 알 수 있다!

백트래킹이 뭔지 모르는 친구에게 백트래킹을 배웠다. 밤낮으로 더 열심히 문제를 풀어야겠다.