inflearn logo
강의

강의

N
챌린지

챌린지

멘토링

멘토링

N
클립

클립

로드맵

로드맵

지식공유

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

7주차 개념 DP(Dynamic Programming)

자두 문제 설명관련 질문드립니다!

162

wldls317

작성한 질문수 15

0

2^30이 언급될 때, 왜 2^30이 언급되는지 잘 이해가 가지 않습니다.

 

선생님께서 2^30에 대해 언급하실 때

자두가 30초 동안 떨어지며 W=30인 것을 가정하고, 이때, 자두의 이동에 대한 모든 경우의 수를 탐색하려면 2^30이 걸린다는 것을 말씀하시는 건가요? (현재 위치 유지하거나/다른 나무로 이동)

 

 

c++ 코딩-테스트

답변 1

0

큰돌

안녕하세요 ㅎㅎ

 

현재 위치 유지하거나/다른 나무로 이동

>>네 맞습니다.

 

문제 지문을 보시면

자두는 T(1≤T≤1,000)초 동안 떨어지게 된다. 자두는 최대 W(1≤W≤30)번만 움직이고 싶어 한다. 매 초마다 어느 나무에서 자두가 떨어질지에 대한 정보가 주어졌을 때, 자두가 받을 수 있는 자두의 개수를 구해내는 프로그램을 작성하시오. 자두는 1번 자두나무 아래에 위치해 있다고 한다.

라고 되어있습니다.자두는 최대 30번움직일 수 있으며 -> 이 때의 경우의 수는 움직이냐 움직이지 않냐 2개의 경우의 수가 있으므로 2^30이 됩니다.

여기서 1000초까지를 왜 생각을 안하냐? 이렇게 물어보실 수 있는데요.

만약 움직이는 횟수를 다 썼다면 -> 그 부분 부터는 계산을 하지 않아도 됩니다.

예를 들어 그 이후 2 2 2 2 2 로 들어오는데 -> 지금 2라면 그저 +만 하면 되기 때문에 이부분에 대한 계산은 들지 않아서 -> 그부분만 계산하면 되고 -> 2^30 이 걸린다고 볼 수 있습니다.

 

감사합니다.

 

코딩테스트 참고문헌 질문

0

30

2

4-P 질문 있습니다.

0

35

3

4-N 문제 수정 요청

0

29

1

2-T 질문

0

38

1

코딩 살구클럽 가입 문의

0

74

2

코딩살구클럽 가입문의

0

79

2

3-K private case 질문

0

76

2

안녕하세요. 코딩살구클럽 문의드립니다!

0

86

2

7:41 듣다가 질문합니다

0

92

2

코드 리뷰 요청드립니다!

0

87

2

코딩살구클럽 계정 문의

0

84

2

SK하이닉스 대비 강의수강

0

226

3

코딩살구클럽 등록부탁드립니다.

0

81

2

7-F 재귀로 풀시 런타임애러

0

82

1

1-N 문제 질문입니다. (+ 채점오류)

0

86

2

코딩살구클럽 가입 확인 부탁드립니다.

0

88

2

직장인 코테 합격 공부방법 문의

0

136

2

코딩살구클럽 가입 방법

0

104

2

6-H 체점 관련 질문

0

83

1

채점서버 연결 관련 질문입니다

0

111

2

삼성 s직군

0

95

1

삼성 코테 없어짐

0

236

1

코딩살구클럽 가입부탁드립니다

0

92

2

코딩살구클럽 가입 요청 확인부탁드립니다

0

77

2