Pembahasan Soal OSP Komputer 2015 Sesi 2 Nomor 5

OK, kali ini saya akan membahas salah satu soal yang saya rasa cukup menarik. Soal ini tidak berhasil saya kerjakan saat OSP (mungkin karena panik), tetapi akhirnya setelah saya coba lagi ternyata solusinya tidak terlalu rumit.

Beginilah soalnya :

Mungkin untuk yang masih belum terbiasa menggunakan rekursi akan sedikit kebingungan, tapi mari kita coba.

Dari soal, informasi yang bisa didapat :

• Banyak langkah untuk menuju suatu petak bergantung pada berapa banyak langkah untuk mencapai petak yang bisa dicapai petak tersebut dengan melompat atau bergerak 1 petak ke arah berlawanan dibanding syarat.
• Banyak langkah menuju sungai bisa dianggap 0.

Dari informasi di atas, kita bisa susun relasi rekurens sebagai berikut :
//x adalah sumbu x (ke timur) dan y adalah sumbu y (ke utara)

    f(x,y) = 1 apabila x=y=1            //basis
    f(x,y) = f(x-1,y)+f(x,y-1)+f(x-2,y)+f(x,y-2), apabila diluar petak atau petak sungai, dianggap 0

Dan untuk menjawab soal di atas, panggil f(6,6).

Berikut tabel memonya :

Sehingga jawaban soal ini adalah 251. Apabila masih bingung dengan rekurens, bisa coba perhatikan pola pada tabel memo, atau tanyakan di bagian komentar (walaupun mungkin akan agak lama baru direspon)

Note : Ini bukanlah solusi official.

CMIIW.