แนวคิด
สมมติว่ามีเหรียญ n เหรียญ ต้องการจัดเป็นรูปบันได ทุกแถวที่ k ต้องมีเหรียญ k เหรียญ ถ้ามี n ให้หาจำนวนแถวบันไดเต็มที่สุดที่สร้างได้
เช่น ถ้าอินพุตคือ 5 ผลลัพธ์คือ 2 ใช้ 5 เหรียญสร้างได้ 2 แถวเต็ม แถวสุดท้ายต้องการ 3 แต่เหลือ 2
*
**
**
สามารถทำได้โดยตรงด้วยสูตร:
$$\frac{\sqrt{(8n+1)}-1}{2}$$
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int arrangeCoins(int n) {
return (sqrt(8*(long long)n+1)-1)/2;
}
};
main() {
Solution ob;
cout << (ob.arrangeCoins(13));
}
อินพุต
13
เอาต์พุต
4
