olleh1597   1년 전

얼마전부터 동적 계획법을 배우기 시작했습니다.

기초적인 문제(배낭에 짐넣기, 1로만들기, 동전쌓기 등...) 들은 원리를 이해 했는데,
문제가 약간이라도 꼬여있으면 알고리즘 짜는것조차 버겁습니다...ㅜㅜ

아래가 제가 지금 골머리를 썩고있는 문제인데,
이 문제를 동적 계획법으로 풀려면 알고리즘을 어떻게 짜면 될지 질문을 드리고 싶습니다.
(사실 이 문제의 어떤 부분에서 동적계획법이 적용되는지 감도 못잡고 있는 상태입니다...)
자세히 코드를 작성해주실 필요 없이, 알고리즘 원리만 설명해주셔도 대단히 감사드리겠습니다.

N명의 학생들이 한 줄로 서 있다.
이 학생들은 모두 키가 다르기 때문에, 모든 학생들이 왼쪽 또는 오른쪽 방향을 바라보면
어떠한 학생들은 앞을 볼 수 있지만, 어떠한 학생들은 앞 사람에게 가려져서 앞을 볼 수가 없다.

예)
키가 150cm 180cm 175cm 177cm 인 학생들이 옆과 같은 순서대로 줄을 서 있다고 할 때
모든 학생들이 왼쪽을 바라보면 150cm, 180cm 학생만 앞을 볼 수 있고,
모든 학생들이 오른쪽을 바라보면 180cm, 177cm 학생만 앞을 볼 수 있다.

전체 학생 수 N, 모든 학생이 왼쪽을 봤을때 앞을 볼 수 있는 학생 수 L, 모든 학생이 오른쪽을 봤을때 앞을 볼 수 있는 학생 수 R 이 주어졌을 때,
N명의 학생들이 줄을 서 있을수 있는 모든 경우의 수의 갯수를 구하시오.

입력)
3 2 2

출력)
2

doju   1년 전

https://www.acmicpc.net/proble...
https://www.acmicpc.net/proble...

f(N, L, R) = 가장 키가 큰 N명의 학생을 왼쪽을 볼 수 있는 학생이 L명, 오른쪽을 볼 수 있는 학생이 R명이 되도록 배치하는 경우의 수
이렇게 상태를 정의하고 점화식을 세워 보세요. 굳이 "가장 키가 큰" 이라는 조건을 붙인 이유는 이미 N명이 배치된 상태에서 그 N명보다 키가 작은 학생을 추가한다는 것이 이 문제의 중요한 아이디어이기 때문입니다.

위와 같이 풀면 O(N3)에 문제를 해결할 수 있으며, 약간의 수학적 지식을 사용하면 O(N2)로도 풀 수 있습니다.

댓글을 작성하려면 로그인해야 합니다.