ได้มีโอกาสไปลองทำโจทย์ บน Online platform มาอันนึง ที่ต้องยอมรับว่า กว่าจะแก้ได้ก็ต้องยอมพ่ายแพ้ ไปค้น discuss board ที่คุยกันถึงแนวคิดในวิธีการแก้โจทย์นี้ ว่าจะทำยังไงอยู่สักพักเลย จนกว่าจะถึงบางอ้อ ก็งงอยู่สักพักนึงเลย
แต่พอเก็ทวิธีแก้โจทย์เท่านั้นล่ะ ถึงกับร้อง อ๋อออออ ลั่นบ้าน แล้วก็เขียนออกมาเป็นโค้ดได้แบบ ไม่ได้ยากเย็นอะไรเลย ซึ่งก่อนหน้าที่จะเข้าใจ Solution นี้ ต้องบอกว่า เขียนวนแล้ววนอีก คิดยังไงก็ไม่ออก งมถูก ๆ ผิด ๆ พอส่งไปเทสกับทุกรูปแบบ ก็ไม่ผ่าน ไม่รู้กี่รอบต่อกี่รอบ
โดยโจทย์ของข้อนี้ จะกำหนด matrix ขนาด 2n x 2n โดยสิ่งที่เราสามารถทำได้คือ reverse row/column แบบไหนก็ได้ เพื่อให้ผลรวมของ quadrant ซ้ายบนที่ n x n มีผลรวมสูงที่สุด
ตัวอย่างโจทย์
ทีนี้ เราจะเขียน Algorithm มายังไงดีล่ะ เพื่อให้สามารถแก้ไขโจทย์ข้อนี้ได้ ?
Problem breakdown
เอาล่ะ ตามโจทย์คือ reverse แนวไหนก็ได้ ทั้ง row/col ซึ่งถ้าเราสังเกตรูปแบบดูดีๆ
เราก็จะเจอจุดที่ค่าสามารถสลับที่กันได้เป็นตามนี้
พอมองเป็นรูปแบบนี้แล้ว พอจะมองเก็ทแล้วยังครับ ว่าเราจะเขียนออกมาเป็นแบบไหน ?
ถ้าเราสังเกตตำแหน่งของแต่ละตัวดูดี ๆ ก็จะพบว่า เราสามารถสลับตำแหน่งของตัวเลขแต่ละจุดหากันได้ทุกมุม
ซึ่งจากโจทย์ คือเราต้องการได้ผลรวมที่สูงที่สุด ของตัวเลขใน quadrant ซ้ายบน เท่ากับว่าเราต้องการได้ผลรวมสูงที่สุดของค่าที่อยู่ภายในวงแดง
ทีนี้พอจะเห็นภาพมากขึ้นแล้วยังครับ ว่าเราจะทำยังไงกับโจทย์ข้อนี้ดี ? สิ่งที่ต้องทำก็จะเหลือแค่ หา maximum ของตัวเลขในชุดที่สามารถสลับตำแหน่งกันได้ เราก็จะได้ผลลัพธ์ตามที่ต้องการออกมาแล้ว … ซึ่งตรงนี้ จะยังขอไม่สปอยโค้ดของโจทย์ข้อนี้แล้วกันนะครับบบบ แต่เอาเป็นว่า ถ้าเขียนโดยใช้ python ก็สามารถใช้ฟังก์ชันสำหรับการหาค่า max มาช่วย แล้วก็เอาตัวเลขที่ได้มาในแต่ละตำแหน่งมา Sum กัน ก็จบล่ะครับ …
วันนี้ก็มาคุยกันประมาณนี้แล้วกันนะครับ ซึ่งจากที่ได้แนวคิดในการทำข้อนี้ออกมาแล้ว ต้องบอกว่าโดยส่วนตัวก็รู้สึกว่าเป็นโจทย์ที่ควรค่าแก่การทำความเข้าใจมาก ๆ เพราะทำให้เรามองปัญหาแตกต่างออกไปพอสมควรเลย ทำให้รู้ว่า บางทีการเขียนโจทย์ออกมา บนกระดาษ ก็ช่วยให้เราได้มองเห็น pattern และได้วิธีการใหม่ที่เป็นการใส่ความคิดสร้างสรรลงไปอีกนิด เพื่อแก้ปัญหาได้ง่ายขึ้นอีกพอสมควรเลย
Key takeaway
ถ้าคิดโจทย์อะไรไม่ออก ลองเอามาวาดเป็นภาพคิดนอกหัวตัวเองดูฮะ 55555
>_JV
