dmsgh7678   9달 전

n을 입력받았을때  nC 2+ nC3+ ....+nCn = 2^n-n-1 ->이 값을 이용하여 3의 n승 까지 n개 필요하다는 것을 구하는 것은 알겠습니다. 

그다음은 어떻게 접근해야 하나요??? 접근 방식을 전혀 모르겠네요... 

일일히 for문으로 값을 구해서 찾자니 시간 에러가 날거 같구....

접근 방식좀 쉽게 설명해주세요..ㅠㅠ

lsc4719   9달 전

N을 3진법으로 나타내라는 거 같아요

lsc4719   9달 전

아 아니구나 그냥 N을 출력하면 답이 되지 않을까요????

dmsgh7678   9달 전

그게 무슨 말인지?..ㅠㅠ 예를 들어 N=4 이다 그러면

1 3 4 9 10 12 13 .......

에서 4를 출력하잖아요.. 

어떻게 접근해야 하나요??ㅠㅠ

lsc4719   9달 전

그렇네요.. 3의 거듭제곱수를 "한번"만 더하니까..

음.. 모든 수가 다음의 연산으로 생성된다는걸 이용하면 되지않을까 하는 아이디어가 있는데요.

시작 조건 x=0

연산1. X 를 3배한다

연산2. X에 1을 더한다

그런데 연산 2번은 연속으로 2번 못한다..

dmsgh7678   9달 전

바쁘신데 도와주셔서 감사합니다.ㅎㅎㅎ


말씀해주신 방법으로는 9 10 12 이경우에서는 9에서 연산2를 해서 10이 됬지만 12로 넘어가지 않을거 같아요...ㅠㅠ 

lsc4719   9달 전

그러네요..ㅠ 

lsc4719   9달 전

N을 롱롱 타입 변수에 저장하면 64비트짜리 비트 어레이가 생기는걸 그걸 하나의 집합으로 보고 풀면 될 것 같아요

lsc4719   9달 전

비트의 위치 인덱스는 3의 지수승을 의미한다고 생각했어요

lsc4719   9달 전

예를들면 n=9이면,

비트열로는 1001로 저장되고

답은 1*(3^3)+0*(3^2)+0*(3^1)+1×(3^0)=28이에요. 3의 거듭제곱들이 '한 번씩'만 쓰일 수 있으니까, 비트들의 0, 1두가지 상태를  각거듭제곱이 더해졌나 안더해졌나 여부로 생각할 수 있어요. 그러면 n의 비트열은, 어떤 3의 거듭제곱을 더했는지를 나타내는 하나의 집합의 표현이 되요. 그리고 각 비트는, ...[3^2][3^1][3^0]이 더해졌나 여부를 의미하게 되요..

dmsgh7678   9달 전

아! 그렇군요 감사합니다 이제 알겠어요!! 꾸벅꾸벅

dmsgh7678   9달 전

말씀해 주신데로 짜보았는데 틀렸다고 나오네요..ㅠㅠ 말씀하신데로 비트로 표현 해 그때 3의 지수승을 더하는 식으로 짰는데 어디가 틀렸을까요??ㅠㅠ 도와주세욥 흑흑..

lsc4719   9달 전

N이 너무커서 int 변수에 담을수가 없어요.

dmsgh7678   9달 전

아! 이런 실수를...ㅠㅠ 감사합니다 해결됬어요!! 꾸벅꾸벅

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