โจทย์ปัญหา
ได้รับตัวเลข ให้หา จำนวนการดำเนินการน้อยที่สุด เพื่อทำให้ทุกหลักเป็น 3 หรือ 8 เท่านั้น โดยการดำเนินการแต่ละครั้งเลือกได้ 1 ใน 2 แบบ:
- บวกหรือลบ 1 จากตัวเลข
- เปลี่ยนหลักใดหลักหนึ่งเป็น 3 หรือ 8
ตัวอย่าง
นำเข้า: 2341974
ผลลัพธ์: 6 operations
แนวคิดการแก้ปัญหา
สังเกตว่า: การเปลี่ยนหลักตัวเลขเป็น 3 หรือ 8 โดยตรง ใช้ 1 Operation ต่อหลัก ในขณะที่การบวก/ลบ 1 อาจส่งผลต่อหลักหลายหลัก (Carry/Borrow) ทำให้ซับซ้อนและมักใช้ Operations มากกว่า
ดังนั้น กลยุทธ์ที่ดีที่สุดคือ: นับหลักที่ไม่ใช่ 3 และไม่ใช่ 8
โค้ดตัวอย่าง (C++)
#include <bits/stdc++.h>
using namespace std;
int calculateMinOperations(long long num) {
int count = 0;
while (num > 0) {
int digit = num % 10;
if (digit != 3 && digit != 8)
count++;
num /= 10;
}
return count;
}
int main() {
long long num = 2341974;
cout << "Minimum Operations: " << calculateMinOperations(num) << endl;
return 0;
}ผลลัพธ์
Minimum Operations: 6คำอธิบายตัวอย่าง 2341974
| Digit | Value | ต้องเปลี่ยน? |
|---|---|---|
| 2 | 2 | ใช่ (→ 3 หรือ 8) |
| 3 | 3 | ไม่ (เป็น 3 แล้ว) |
| 4 | 4 | ใช่ |
| 1 | 1 | ใช่ |
| 9 | 9 | ใช่ |
| 7 | 7 | ใช่ |
| 4 | 4 | ใช่ |
| Total | 6 Operations |
คำอธิบายเพิ่มเติม
- Time Complexity: O(log n) (จำนวนหลักของตัวเลข)
- Space Complexity: O(1)
- สมมติฐาน: การ "เปลี่ยนหลัก" ใช้ Cost = 1 เท่ากับ "บวก/ลบ 1"
- ถ้า Cost ต่างกัน (เช่น เปลี่ยนหลัก Cost=2, บวก/ลบ Cost=1) จะต้องใช้ DP/Graph Search
- โจทย์นี้เป็น Greedy ที่ Optimal เพราะแต่ละหลักเป็นอิสระต่อกัน (No Carry/Borrow effect เมื่อเปลี่ยนหลักโดยตรง)
