[Golang으로 도전하는 Leetcode] Minimum Cost For Tickets

오늘 풀 문제는 Minimum Cost For Tickets라는 문제이며

링크는 https://leetcode.com/problems/minimum-cost-for-tickets/ 입니다

 

문제는 day의 배열을 받아서 각각의 day마다 여행을 하는데 1-pass, 7-pass, 30-pass 여행티켓을 골라서

가장 최소로 여행을 끝내는 비용이 얼마인지 구하는 문제였습니다

여행티켓가격은 costs배열로 들어옵니다

이 문제는 저는 다이나믹 프로그래밍으로 풀었습니다

지금 날짜가  i라고 했을 때 i-1일의 날짜에서 1-pass 가격을 더한 비용과 i-7일 날짜에서 7-pass 가격을 더한 비용과

i-30일 날짜에서 30-pass 가격을 더한 비용중 가장 적은 비용이 i 날짜의 비용이라고 생각하고 접근하였습니다

그리고 만약에 i라는 날짜가 days 배열에 없다면 조건에서 연속적인 날짜로 pass 비용이 된다고 했으니

i-1 날짜의 비용과 같다고 생각하였습니다

이 접근 방법으로 푼 코드입니다

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
func max(a, b int) int {
	if a >= b {
		return a
	}
	return b
}

func mincostTickets(days []int, costs []int) int {
	var dp = make([]int, 366, 366)
	max_day := days[len(days)-1]
	for d, i := 1, 0; d <= max_day; d++ {
		if d == days[i] {
			dp[d] = min(min(dp[d-1]+costs[0], dp[max(0, d-7)]+costs[1]), dp[max(0, d-30)]+costs[2])
			i++

		} else {
			dp[d] = dp[d-1]
		}

	}
	return dp[max_day]
}

 

읽어주셔서 감사합니다