처음 구현은 N에서 N의 약수를 하나 씩 빼보고, 음수가 나오면 이전의 약수를 다시 더해서 양수로 만들어 다시 그 다음 약수를 하나씩 빼주는 형태로 구현했었는데요, 중간에 N에서 약수를 빼서 0이 나오면 조건이 만족되지 않으므로 입력을 주고 종료시키는 식으로요. 이렇게 구현하면 예제에 있는 12, 70은 제가 원하는 대로 나오지만 댓글에 달린 1575, 1870, 2530, 2958 중에는 오류가 발생합니다.
알고리즘 책도 잘 이해는 안되지만 보고 있어서 동적계획법을 사용해야 하나 싶은데 제가 이해한 대로라면 12, 70은 약수가 5개, 6개 뿐이니까
위와 같은 형태로 만들어서 매번 확인을 해주고 -1이 아니라면 결과를 적고 종료하는 식으로 재귀호출을 하면 될 것 같은데 댓글에 달린 1575, 1870, 2530, 2958 중에 약수가 13개인 경우도 있으며 입력을 받을 때마다 for문을 중첩해서 동적할당을 받는 것도 너무 과도한 양인 것 같아서 문제 해결을 어떤 방법으로 해야 할 지 모르겠습니다. 혹시 힌트를 좀 주실 수 있을까요.
6년 전
0개의 댓글이 있습니다.
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면
온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야
합니다. 현재 문제를 푸셨습니다.
ultimate1994
WEIRD 문제에 나오는 두 조건 중에
약수의 부분 집합의 합이 N이 아니어야 한다는 조건 때문에 질문드립니다.
제가 아직 알고리즘에 초보라서 이 부분을 어떤 식으로 처리해야 할 지 감이 전혀 안와요.
처음 구현은 N에서 N의 약수를 하나 씩 빼보고, 음수가 나오면 이전의 약수를 다시 더해서 양수로 만들어 다시 그 다음 약수를 하나씩 빼주는 형태로 구현했었는데요, 중간에 N에서 약수를 빼서 0이 나오면 조건이 만족되지 않으므로 입력을 주고 종료시키는 식으로요. 이렇게 구현하면 예제에 있는 12, 70은 제가 원하는 대로 나오지만 댓글에 달린 1575, 1870, 2530, 2958 중에는 오류가 발생합니다.
알고리즘 책도 잘 이해는 안되지만 보고 있어서 동적계획법을 사용해야 하나 싶은데 제가 이해한 대로라면 12, 70은 약수가 5개, 6개 뿐이니까
위와 같은 형태로 만들어서 매번 확인을 해주고 -1이 아니라면 결과를 적고 종료하는 식으로 재귀호출을 하면 될 것 같은데 댓글에 달린 1575, 1870, 2530, 2958 중에 약수가 13개인 경우도 있으며 입력을 받을 때마다 for문을 중첩해서 동적할당을 받는 것도 너무 과도한 양인 것 같아서 문제 해결을 어떤 방법으로 해야 할 지 모르겠습니다. 혹시 힌트를 좀 주실 수 있을까요.
6년 전