글 읽기 - 1칸씩 뛰는 개구리 있는지요?

srand 5년 전 0

최대 6칸 간격 이라는 제한은 있는데,

최소는 없어서 1칸 이라 가정 해도 무방한지요. ?

최대 : 6칸.
    
2  3  4  5  6  7  8  9  10 11 12
0  0  0  0  1  0  0  0  0  0  1     => 6 6  (doju님 답변으로 추가)
0  0  0  1  0  0  0  0  0  1  0     => 5 6
0  0  1  0  0  0  0  0  1  0  0     => 4 6
0  1  0  0  0  0  0  1  0  0  0     => 3 6
1  0  0  0  0  0  1  0  0  0  0     => 2 6
0  0  0  0  0  1  0  0  0  0  0     => 1 6
    

최소 : 1칸
2  3  4  5  6  7  8  9  10 11 12
1  1  1  1  1  1  1  1  1  1  1     => 1 1

doju 5년 전 1

최소는 1칸(1 1 개구리)입니다. 오해하신 부분이 있는 것 같아 덧붙이면 <그림 3>에는 4 4 개구리가 등장합니다.

srand 5년 전 0

@doju 감사합니다 ^^

srand 5년 전 0

@doju 덕분에 풀었네요. ^^

doju 5년 전 1

개인적으로 다른 사람들은 이 문제를 어떻게 푸는지 궁금한데, 혹시 접근 방법을 대략적으로 설명해 주시거나 코드를 공개해 주실 수 있나요? 🙇

srand 5년 전 1

저는...

개구리 뛰는것을 1차 방정식으로 만들어서 가우스 소거법으로 풀고

미지수 8개? 9개? 정도를 backtracking 돌렸습니다.

srand 5년 전 0

1차 방정식은 총 21개 ( 초기에.. 1칸씩 뛰는걸 빼고 20개만 돌렸었네요.. ;; ) 이고

그 해는 뛰는 방법의 횟수가 될테고,

총 합은 100보다 작거나 같고,

각 변수에 대해 min, max range 구해서 cut 했습니다. ^^

doju 5년 전 1

답변 감사합니다! 제 풀이는 개구리의 종류가 달라지면 완전히 갈아엎어야 하는데 뚝딱 고쳐서 정답을 받으시길래 신기했습니다. 제가 추가한 데이터들도 검증해 주셔서 감사합니다 :D

미지수가 8~9개라면 잘 하면 시간 초과를 낼 수도 있을 것 같지만.. 😈

srand 5년 전 2

샘플 데이터 생성해서 테스트 해봤을때

1차 방정식

X1 = 1x+1의 개수

X2 = 2x+1의 개수

X3 = 2x+2 의 개수

...

X21 = 6x+6의 개수

X1 ~ X21의 값을 찾기 위해

backtracking으로 3depth (X1 ~ X3) 까지는 보통 0 부터 100 까지 min, max range를 갖는데 그 이후 부터는 많이(?) 좁혀지고

8~9 depth 정도 들어가면 변수값들이 모두 정해지더라구요.. (물론 input에 따라 다르겠지만요..)

0 ~ 100 까지 range를 갖는 변수가 5개 이상이 되면 TLE가 나와야 할텐데,

아직은 그런 input이 없는 듯 하네요.

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