สมมติว่าเรามีกริดขนาด n×3 และเราต้องการทาสีทุกเซลล์ของกริดด้วยสีเพียงหนึ่งสีจากสามสี ได้แก่ แดง เหลือง และเขียว
มีเงื่อนไขคือ ไม่มีเซลล์ติดกันสองเซลล์ที่มีสีเหมือนกัน เรามี n แถวของกริด สุดท้ายเราต้องหาจำนวนวิธีที่เราสามารถทาสีกริดนี้ได้ คำตอบอาจใหญ่มาก จึงคืนค่าโมดิวโล 10^9 + 7
เช่น ถ้าอินพุตคือ 1 ผลลัพธ์จะเป็น 12
ในการแก้ปัญหานี้ เราจะทำตามขั้นตอนต่อไปนี้:
- m = 10^9 + 7
- กำหนดฟังก์ชัน add() รับ a, b คืนค่า ((a mod m) + (b mod m)) mod m
- จาก main method: a123 := 6, a121 = 6
- ลูป i จาก 2 ถึง n: b121 := add(3 * a121, 2 * a123), b123 := add(2 * a121, 2 * a123), a121 := b121, a123 := b123
- คืนค่า add(a123, a121)
ตัวอย่าง
ลองดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli mod = 1e9 + 7;
class Solution {
public:
lli add(lli a, lli b) {
return ((a % mod) + (b % mod)) % mod;
}
int numOfWays(int n) {
lli a123 = 6, a121 = 6;
lli b123, b121;
for (int i = 2; i <= n; i++) {
b121 = add(3 * a121, 2 * a123);
b123 = add(2 * a121, 2 * a123);
a121 = b121;
a123 = b123;
}
return add(a123, a121);
}
};
main() {
Solution ob;
cout << (ob.numOfWays(3));
}
อินพุต
3
เอาต์พุต
246
