글 읽기 - 1029번 조건이 빠져있는것 같습니다.

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

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

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

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

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

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

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

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

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

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

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

확실친 않아요.. ㅠㅠ

DP가 아니라 BFS요 ㅋㅋㅋ

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

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

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

조언 감사합니다!

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

Baekjoon Online Judge