오늘 푼 문제
-
문자열
- 12904 A와 B - 생각을 반대로!
- 2671 잠수함 식별 - 정규표현식을 이용한 match 문제
- 4358 생태학 - 그냥... 문제
-
DP
- 11060 점프 점프 - 최소한의 점프로 도착하는 문제
- 15988 1,2,3 더하기 3 - 1,2,3으로 만들 수 있는 경우의 수 출력
- 15990 1,2,3 더하기 5 - 위의 문제 + 특수한 조건
-
그래프
- 1446 지름길 - 단뱡향의 경우 문제를 다르게 풀 수도 있구나
- 17396 백도어 - 단방향과 양방향의 경우 다른 점을 생각하느라 시간 걸린 문제.
문제 푼 흔적
기억할 만한 아이디어
12904 A와B
링크 : https://www.acmicpc.net/problem/12904
A와 B로 이루어진 문자 2개 (X,Y)를 주어주고, 2가지의 변형 방법을 적용하여 X를 Y로 바꿀 수 있는지 여부를 묻는 문제이다.
예전에 비슷한 문제를 풀었었는데, 그 때에도 bfs 방식을 통해서 X-->Y로 가는 문자열들을 찾아서 시간초과/메모리초과 를 받았었다.
주어진 조건을 반대로 적용하여 Y-->X로 찾아가면 훨씬 빠르게 동작하더라.
결론 : 반대 방향에서도 생각해 볼 것
1446 지름길
링크 : https://www.acmicpc.net/problem/1446
직접적인 노드를 주지 않았던 문제라 많이 당황했었다. 단방향 문제라 앞 부터 차근차근 비교해 나가면 됬던 문제. Dp 유형과 똑같더라.
위 문제를 풀고 17396번을 풀다보니 잠시 헷갈렸는데, 양방향 간선이 경우에는 내가 방문할 수 있는 모든 노드를 체크해 주어야 하기 때문에, 단순히 for문 한 번 돌아가는 정도로 문제를 해결할 수 없다.
FE 임니다