Artechno Festival Programming Competition – Rute Maksimal (B)

Soal ini merupakan soal lain yang dibuat oleh Bapak Mohammad Andri Budiman.

Perhatikan segitiga berikut:

Tulis program untuk menghitung nilai terbesar dari angka-angka yang ada dalam jalur yang dimulai dari atas sampai ke bawah. Setiap langkah dalam jalur dapat secara diagonal ke bawah kiri atau kanan.

Pada contoh di atas, nilai terbesar adalah 30, diperoleh dari jalur 7-3-8-7-5.

Input:
Input diawali bilangan bulat T (1 <= T <= 1000) yakni banyaknya test case.
Untuk setiap test case, diberikan bilangan bulat N (1 < N <=100) yang merupakan ukuran segitiga. N baris berikutnya berisi bilangan bulat X (0 <= X <= 99) yang merupakan angka pada setiap baris segitiga.

Output:
Untuk setiap test case, tampilkan sebuah baris berisi bilangan bulat yang merupakan jumlah terbesar yang didapat dari rute yang dijelaskan di atas.

Contoh input:
2
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
2
1
1 1

Contoh output:
30
2

———-

Pada dasarnya, dari setiap posisi angka dalam segitiga, kita boleh turun ke kiri atau ke kanan. Jika digambarkan, menjadi seperti di bawah ini (hanya beberapa jalur yang digambarkan):

Jika setiap angka kita rapatkan ke kiri, segitiga tersebut akan menjadi seperti ini:

Untuk menyelesaikannya, kita perlu meng-update angka di setiap posisi. Angka hasil update ini menunjukkan berapa hasil penjumlahan terbesar yang dapat dilakukan dari posisi tersebut ke bawah.

Pertama lihat baris terakhir (yang berisi angka 4, 5, 2, 6, 5). Karena ini paling bawah tentu saja tidak mungkin lagi untuk turun. Maka angka di baris ini tidak ada yang di-update.

Selanjutnya perhatikan baris kedua dari bawah (yang berisi angka 2, 7, 4, 4).

Dari posisi angka 2 (angka pertama dari kiri), kita bisa turun ke angka 4 atau turun ke angka 5. Jika turun ke angka 4, kita bisa memperoleh jumlah 6 (diperoleh dari menambahkan angka di posisi saat ini [yaitu 2] dengan angka di posisi tujuan [yaitu 4]). Jika turun ke angka 5, kita bisa memperoleh jumlah 7 (diperoleh dari menambahkan angka di posisi saat ini [yaitu 2] dengan angka di posisi tujuan [yaitu 5]). Maka dari posisi ini, kita bisa mendapatkan jumlah 6 atau 7. Yang terbesar (pada gambar diberi istilah best) adalah 7. Sehingga, kita update angka di posisi ini menjadi 7.

Selanjutnya dari posisi angka 7 (angka kedua dari kiri), kita bisa turun ke angka 5 sehingga memperoleh jumlah 12 atau turun ke angka 2 sehingga memperoleh jumlah 9. Yang terbesar adalah 12. Update angka di posisi ini menjadi 12.

Begitu selanjutnya hingga semua angka di baris tersebut telah di-update. Pada hasil akhir, kita akan memperoleh angka 7, 12, 10, 10 di baris ini.

Setelah satu baris selesai, lanjut ke baris berikutnya (baris ketiga dari bawah). Lakukan hal yang sama seperti sebelumnya. Maka hasil akhir di baris ini akan seperti ini:

Baris selanjutnya (baris keempat dari bawah) akan menghasilkan ini:

Baris selanjutnya (baris kelima dari bawah — yaitu baris terakhir [paling atas]) akan menghasilkan ini:

Karena sudah tidak ada lagi baris yang akan diproses, maka angka yang terletak di baris terakhir (paling atas) tersebut adalah jawaban yang diminta.

Berikut ini merupakan contoh solusi dalam bahasa Java:

import java.util.Scanner;

public class B {

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);

        int nTC = sc.nextInt();
        while (nTC-- > 0) {
            int N = sc.nextInt();

            int[][] segitiga = new int[N][N];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j <= i; j++) {
                    segitiga[i][j] = sc.nextInt();
                }
            }

            // mulai dari baris ke-2 dari bawah sampai paling atas
            for (int i = N - 2; i >= 0; i--) {
                for (int j = 0; j <= i; j++) {
                    // mana yg lebih optimal, turun ke kiri (segitiga[i + 1][j]) atau ke kanan (segitiga[i + 1][j + 1])?
                    int best = Math.max(segitiga[i][j] + segitiga[i + 1][j], segitiga[i][j] + segitiga[i + 1][j + 1]);
                    segitiga[i][j] = best; // update!
                }
            }

            System.out.println(segitiga[0][0]); // angka di paling atas sekarang adalah yg maksimum
        }
    }

}

Input dan output yang digunakan juri dapat dilihat di sini.