23/10/07

[알고리즘]

1. 백준 - 2591 숫자카드

• TopDown, BottomUp 모두 가능
• 10, 20, 30과 같은 카드에서 나오는 0을 고려하지 않으면 틀린다.
• 그나마 쉬움

2. 백준 - 15486 퇴사2

• BottomUp이 Python은 되는데 Java로는 안됨
• 역순으로 마지막 날부터 앞으로 가면서 상담을 한 경우와 그렇지 않은 경우를 비교
• 그나마 쉬움

3. 백준 - 5557 1학년

• 해설 봄 (복습 필요)
• 핵심 : 가장 처음 카드는 이미 사용했다 치고 그 다음 숫자를 더하거나 뺀다.
  • 마지막에 도착하고 목표 숫자가 맞다면 경우의 수 + 1
  • 이미 값이 나왔거나 조건에 맞지 않으면 반환한다.
  • 더하거나 빼는 경우를 다 포함하기 위해 DP함수를 각각 호출해야한다.
• 약간 어려움

4. 백준 - 2758 로또

• Bottom Up이 또 안됨 ㅡㅡ
• '특정한 숫자'를 만드는게 아니라, 모든(누적) 경우의 수를 찾는 것이다.
• 따라서 `dp[숫자 순서][고른 숫자]` 의 값은, 이전에 만들어진 경우도 누적한다.
• 그렇게하면 가장 마지막 위치에서 모든 경우의 수를 얻을 수 있다.
• 어려움

5. 백준 - 1106 호텔

• C명 이상을 만족하는 최소 비용
• 'C명 이상' 이라는 점에서, C를 초과하는 최소비용도 고려해야한다.
• 도시 하나씩 보면서 이제까지 cnt명일 때 얼마였는지 비교한다.
• 한 도시에서 '정수배'로 사람과 비용을 투자할 수 있기 때문에 여러번 사용할 수 있다.
• 따라서 사람 한명 한명씩 늘려가며 비용을 계산해야한다.

• 어려움

6. 백준 - 1520 내리막길

• DFS와 메모이제이션을 활용한다.
• 각 루트를 가면서 이 위치에 몇번의 경우로 도착할 수 있는지 보는건 맞다.
• 대신 이동할 때 DFS를 활용해서 끝까지 한번 간다.
• 그러면 오는 길에 경우의 수들이 누적되고, 나중에는 끝까지 가지 않아도 경우의 수를 활용할 수 있다.

7. 백준 - 7579 앱

• 보통 dp 테이블의 '값'이 정답인데, '인덱스' 가 정답인 케이스
• 왜냐하면 메모리 최대값이 너무 크기 때문이다.
• dp[비용] = 찾을 수 있는 최대 메모리 크기
• 비용은 역순으로 순회해야 같은 앱을 2번 이상 비활성화 시키는 일이 일어나지 않는다.