3, 5 ve 10 puan almanın mümkün olduğu ve hedef puana bu puan gruplarını kullanarak kaç farklı şekilde ulaşılabileceğini bulacağız.

Örnek;

Input: n = 20
Output: 4
(10, 10)
(5, 5, 10)
(5, 5, 5, 5)
(3, 3, 3, 3, 3, 5)

Input: n = 13
Output: 2
(3, 5, 5)
(3, 10)

Çözüm mantığı gayet basittir. n+1 boyutunda bir dizi yaratılır ve her puanlama için döngüler ile tüm çözüm sayıları tutulur. Zaman ve yer karmaşıklığı 0(n) olacaktır.

def adjust(l, score, n):
    for i in range(score, n + 1):
        l[i] += l[i - score]


def count(n):
    result = [0] * (n + 1)
    result[0] = 1  # 0 puan için

    adjust(result, 3, n)
    adjust(result, 5, n)
    adjust(result, 10, n)

    return result[n]

if __name__ == '__main__':
    score = 20
    print(count(score))

Cevabı doğru bulduk fakat (10, 5, 5), (5, 5, 10) ve (5, 10, 5) durumları tek bir durum olarak sayılmıştır. Peki bu durumlarıda farklı birer yol olarak saymak istersek yukarıdaki kodu biraz değiştirmek gerekecek.

def count_new(n):
    result = [0] * (n + 1)
    result[0] = 1  # 0 puan için

    for i in range(3, n + 1):
        if i >= 3:
            result[i] += result[i - 3]
        if i >= 5:
            result[i] += result[i - 5]
        if i >= 10:
            result[i] += result[i - 10]

    return result[n]

if __name__ == '__main__':
    score = 20
    print(count_new(score))

Comments

comments powered by Disqus