[Programmers] Level 3

문제 목록 바로가기 : https://programmers.co.kr/learn/challenges

가장 긴 팰린드롬

Link : https://programmers.co.kr/learn/courses/30/lessons/12904

solution

어떻게 풀어볼까 고민하다가 문자열 최대 길이가 생각보다 길지 않아서 간단하게 풀었다.
범위가 좀만 커졌어도 TLE 받기 쉬울 것 같은데 나중엔 범위가 긴 문제로 한 번 풀어봐야겠다.

블록 이동하기

Link : https://programmers.co.kr/learn/courses/30/lessons/60063

solution

BFS 문제다. 범위 밖으로 나가지 않도록 그리고 벽과 부딪히지 않도록 설정해주는게 전부다.
이게 전부지만 직접 짜보려 하면 좀 귀찮다. 회전하는 경우 코드를 줄여 쓸 생각이 떠오르지 않았다.
로봇이 가로로 있을 때, 세로로 있을 때 각각의 경우를 또한 체크해줘야 한다.
구현이 좀 빡센 BFS라고 생각한다.

거스름돈

Link : https://programmers.co.kr/learn/courses/30/lessons/12907

solution

DP 유형이다. 재귀를 통해 메모이제이션을 처음에 이용했는데 효율성 테스트에서 시간 초과를 받았다.
왜 메모리 초과말고 시간 초과를 받았는지 잘 모르겠지만.. 결론적으로 이 문제는 1차원 배열만으로 해결이 가능하다.
화폐 단위들을 정렬해준 후 진행해야 한다.
BOJ 2293: 동전 1과 같은 문제.

리틀 프렌즈 사천성

Link : https://programmers.co.kr/learn/courses/30/lessons/1836

solution

이게 브루트 포스로 해결이 될까 생각을 해보다가 조금 간단하게 풀 수 있는 방법이 생각났다.
결론적으로는 브루트 포스로도 풀 수 있지만 내가 푼 방법은 다음과 같다.
구현이 어렵진 않았다. 다만 break문 1개를 잘못써서 내내 고생했다..

1. 같은 알파벳은 총 2번만 등장한다. 각각을 출발점, 도착점으로 설정한다.
2. 출발점으로부터 도착점으로 갈 때는 1번만 꺾어야 하므로 가로->세로, 세로->가로 2가지 케이스를 계산한다.
3. 출발점에서 도착점으로 도달 가능한 경우 모두 이동가능한 점 ‘.’으로 바꿔준다.

멀리 뛰기

Link : https://programmers.co.kr/learn/courses/30/lessons/12914

solution

단순 DP 유형. 오버플로우에 주의하기!
\(f(n) = f(n-1) + f(n-2)\)

방문 길이

Link : https://programmers.co.kr/learn/courses/30/lessons/49994

solution

걸었던 길 중 중복되지 않는 길의 길이를 구해야 한다.
크게 어렵지는 않지만 특정 길을 앞뒤로 갔을 때 2번 카운트되지 않도록 하는게 포인트.