yukariko   2년 전

1번 예술가는 외부상인에게 그림을 샀다고 나와있는데 얼마에 샀는지를 알려줘야 하지 않을까요?

만약 외부상인에게 산 그림은 조건에 포함하지 않는다면,  2번 조건의

2. 같은 그림을 한 번 이상 사는 것은 불가능하다.

의 조건 또한 포함되지 않아서 1번 예술가는 결과적으로 그림을 2번 살 수 있어야 맞는거니까요.

제가 이걸 질문에 올린이유는 추가로 여쭈어볼것이 있어서 그런데

제가 짠 소스로는 dfs 를 이용해서 시간복잡도가 O(n!) 이 나오더군요.. 근데 아무리 생각해도 n!말고는 생각이 잘 안나는데

혹시 맞추신분들은 시간복잡도가 어떻게 되시는지요?

1번 예술가가 외부 상인에게 0원에 그림을 구매한셈 치고 풀었더니 오류가 없어여

지금 제 코드는 몇달전에 어거지로 DFS랑 이것저것 섞어서 푼거지만.. 지금 보니 DP로 될거같네요

저장하는 값은 N번째 예술가가 / K원에 그림을 샀고 / 아직 그림을 구매한 적 없는 예술가 목록은 이러하다(비트마스킹 같은 걸로?)

각각 값 저장하는 3차원 배열 만들고 요렇게 해서 돌리면 나올거 같네용

확실친 않아요.. ㅠㅠ

DP가 아니라 BFS요 ㅋㅋㅋ

yukariko   2년 전

그렇군요.. 역시 아직 구매하지 않은 목록을 표시를 해놔야 겠네요.

그것이 DFS는 그냥 1차원 배열 1개로도 가능했는데 뭔가 생각이 복잡해져서 ㅠㅠ

이것저것 궁리해봐야 할 것 같습니다.

조언 감사합니다!

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