Olimpiade Sains Kota (OSK) 2016 - Komputer, Nomor 38
Pak Dengklek ingin membawa belanjaannya dari pasar ke rumahnya hanya melalui suatu jaringan jalan tol. Pada setiap ruas jalan tol ia harus membayar sejumlah uang yang ditunjukkan dengan angka-angka pada gambar berikut.
Ia ingin memilih lintasan dengan biaya yang paling minimum. Berapa biaya minimum yang harus disediakan Pak Dengklek untuk sampai ke rumahnya?
a. 17
b. 18
c. 19
d. 20
e. 21
5 jawaban
Fariz Wakan10 tahun lalu
#OSN2016
6
Teknik yang tepat untuk mengerjakan soal ini dengan DP (Dynamic Programming).
Dengan menyimpan penjumlahan angka terkecil (garis dan titik sebelumnya) di setiap Vertex-nya (Titik).
Jadi, Jawabannya 19 (C)
Bagas Pangestu 10 tahun lalu
1
yang diminta adalah biaya minimum, diperoleh 19.
Fransiscus Emmanuel Bunaren9 tahun lalu
1
Jalan dengan biaya paling minimum sebanyak 19
Dari rumah, ambil jalan nomor 3 => 2 => 11 => 3 => Sampai
Masuk untuk menulis jawaban
TOKI 2012, IF ITB 2012. http://olimpiadeinformatika.com
Istilah Greedy sepertinya kurang tepat. Karena berdasarkan definisi, Greedy akan mengambil pilihan terbaik (saat ini) untuk setiap langkah. Sehingga pada langkah pertama (kalau Greedy) akan memilih jalan dengan panjang 2, karena paling pendek diantara pilihan lain.
Jawaban benar, namun menurut saya sebaiknya tidak menggunakan istilah Greedy. Takut menyesatkan. Hehehe