λͺ©λ‘π¦₯ μ½ν /BAEKJOON (287)
π 곡λΆνλ μ§μ§μνμΉ΄λ μ²μμ΄μ§?
ν΄λ¦¬μ€λ―Έλ Έλ ν¬κΈ°κ° 1×1μΈ μ μ¬κ°νμ μ¬λ¬ κ° μ΄μ΄μ λΆμΈ λν μ μ¬κ°νμ μλ‘ κ²ΉμΉλ©΄ μ λλ€. λνμ λͺ¨λ μ°κ²°λμ΄ μμ΄μΌ νλ€. μ μ¬κ°νμ λ³λΌλ¦¬ μ°κ²°λμ΄ μμ΄μΌ νλ€. μ¦, κΌμ§μ κ³Ό κΌμ§μ λ§ λ§λΏμ μμΌλ©΄ μ λλ€. μ μ¬κ°ν 4κ°λ₯Ό μ΄μ΄ λΆμΈ ν΄λ¦¬μ€λ―Έλ Έλ ν νΈλ‘λ―Έλ Έ μλ¦μ΄λ ν¬κΈ°κ° N×MμΈ μ’ μ΄ μμ ν νΈλ‘λ―Έλ Έ νλλ₯Ό λμΌλ €κ³ νλ€. μ’ μ΄λ 1×1 ν¬κΈ°μ μΉΈμΌλ‘ λλμ΄μ Έ μμΌλ©°, κ°κ°μ μΉΈμλ μ μκ° νλ μ°μ¬ μλ€. ν νΈλ‘λ―Έλ Έ νλλ₯Ό μ μ ν λμμ ν νΈλ‘λ―Έλ Έκ° λμΈ μΉΈμ μ°μ¬ μλ μλ€μ ν©μ μ΅λλ‘ νλ νλ‘κ·Έλ¨μ μμ± ν νΈλ‘λ―Έλ Έλ λ°λμ ν μ μ¬κ°νμ΄ μ νν νλμ μΉΈμ ν¬ν¨νλλ‘ λμμΌ νλ©°, νμ μ΄λ λμΉμ μμΌλ λλ€. 첫째 μ€μ μ’ μ΄μ μΈλ‘ ν¬κΈ° Nκ³Ό κ°λ‘ ν¬κΈ° Mμ΄ μ£Όμ΄μ§λ€. (4..
ν¬κΈ°κ° N×MμΈ μ§λκ° μ‘΄μ¬νλ€. μ§λμ μ€λ₯Έμͺ½μ λμͺ½, μμͺ½μ λΆμͺ½μ΄λ€. μ΄ μ§λμ μμ μ£Όμ¬μκ° νλ λμ¬μ Έ μμΌλ©°, μ§λμ μ’νλ (r, c)λ‘ λνλ΄λ©°, rλ λΆμͺ½μΌλ‘λΆν° λ¨μ΄μ§ μΉΈμ κ°μ, cλ μμͺ½μΌλ‘λΆν° λ¨μ΄μ§ μΉΈμ κ°μ μ£Όμ¬μλ μ§λ μμ μ λ©΄μ΄ 1μ΄κ³ , λμͺ½μ λ°λΌλ³΄λ λ°©ν₯μ΄ 3μΈ μνλ‘ λμ¬μ Έ μμΌλ©°, λμ¬μ Έ μλ κ³³μ μ’νλ (x, y) μ΄λ€. κ°μ₯ μ²μμ μ£Όμ¬μμλ λͺ¨λ λ©΄μ 0μ΄ μ νμ Έ μλ€. μ§λμ κ° μΉΈμλ μ μκ° νλμ© μ°μ¬μ Έ μλ€. μ£Όμ¬μλ₯Ό κ΅΄λ Έμ λ, μ΄λν μΉΈμ μ°μ¬ μλ μκ° 0μ΄λ©΄, μ£Όμ¬μμ λ°λ₯λ©΄μ μ°μ¬ μλ μκ° μΉΈμ 볡μ¬λλ€. 0μ΄ μλ κ²½μ°μλ μΉΈμ μ°μ¬ μλ μκ° μ£Όμ¬μμ λ°λ₯λ©΄μΌλ‘ 볡μ¬λλ©°, μΉΈμ μ°μ¬ μλ μλ 0μ΄ λλ€. μ£Όμ¬μλ₯Ό λμ κ³³μ μ’νμ μ΄..
κ²μμλ λ±μ΄ λμμ κΈ°μ΄λ€λλλ°, μ¬κ³Όλ₯Ό λ¨ΉμΌλ©΄ λ± κΈΈμ΄κ° λμ΄λλ€. λ±μ΄ μ΄λ¦¬μ 리 κΈ°μ΄λ€λλ€κ° λ²½ λλ μκΈ°μμ μ λͺΈκ³Ό λΆλͺνλ©΄ κ²μμ΄ λλλ€. κ²μμ NxN μ μ¬κ° 보λμμμ μ§νλκ³ , λͺλͺ μΉΈμλ μ¬κ³Όκ° λμ¬μ Έ μλ€. 보λμ μνμ’μ° λμ λ²½μ΄ μλ€. κ²μμ΄ μμν λ λ±μ 맨μ 맨μ’μΈ‘μ μμΉνκ³ λ±μ κΈΈμ΄λ 1 μ΄λ€. λ±μ μ²μμ μ€λ₯Έμͺ½μ ν₯νλ€. λ±μ 맀 μ΄λ§λ€ μ΄λμ νλλ° λ€μκ³Ό κ°μ κ·μΉμ λ°λ₯Έλ€. λ¨Όμ λ±μ λͺΈκΈΈμ΄λ₯Ό λλ € 머리λ₯Ό λ€μμΉΈμ μμΉμν¨λ€. λ§μ½ μ΄λν μΉΈμ μ¬κ³Όκ° μλ€λ©΄, κ·Έ μΉΈμ μλ μ¬κ³Όκ° μμ΄μ§κ³ 꼬리λ μμ§μ΄μ§ μλλ€. λ§μ½ μ΄λν μΉΈμ μ¬κ³Όκ° μλ€λ©΄, λͺΈκΈΈμ΄λ₯Ό μ€μ¬μ κΌ¬λ¦¬κ° μμΉν μΉΈμ λΉμμ€λ€. μ¦, λͺΈκΈΈμ΄λ λ³νμ§ μλλ€. μ¬κ³Όμ μμΉμ λ±μ μ΄λκ²½λ‘κ° μ£Όμ΄μ§ λ ..
ν λ²μ μ΄λμ 보λ μμ μλ μ 체 λΈλ‘μ μνμ’μ° λ€ λ°©ν₯ μ€ νλλ‘ μ΄λμν€λ κ² κ°μ κ°μ κ°λ λ λΈλ‘μ΄ μΆ©λνλ©΄ λ λΈλ‘μ νλλ‘ ν©μ³μ§κ² λλ€. ν λ²μ μ΄λμμ μ΄λ―Έ ν©μ³μ§ λΈλ‘μ λ λ€λ₯Έ λΈλ‘κ³Ό λ€μ ν©μ³μ§ μ μλ€. (μ€μ κ²μμμλ μ΄λμ ν λ² ν λλ§λ€ λΈλ‘μ΄ μΆκ°λμ§λ§, μ΄ λ¬Έμ μμ λΈλ‘μ΄ μΆκ°λλ κ²½μ°λ μλ€) λκ°μ μκ° μΈ κ°κ° μλ κ²½μ°μλ μ΄λνλ €κ³ νλ μͺ½μ μΉΈμ΄ λ¨Όμ ν©μ³μ§λ€. μ΄ λ¬Έμ μμ λ€λ£¨λ 2048 κ²μμ 보λμ ν¬κΈ°κ° N×N μ΄λ€. 보λμ ν¬κΈ°μ 보λνμ λΈλ‘ μνκ° μ£Όμ΄μ‘μ λ, μ΅λ 5λ² μ΄λν΄μ λ§λ€ μ μλ κ°μ₯ ν° λΈλ‘μ κ°μ ꡬνλ νλ‘κ·Έλ¨μ μμ± μ²«μ§Έ μ€μ 보λμ ν¬κΈ° N (1 ≤ N ≤ 20)μ΄ μ£Όμ΄μ§λ€. λμ§Έ μ€λΆν° Nκ°μ μ€μλ κ²μνμ μ΄..
κ΅¬μ¬ νμΆμ μ§μ¬κ°ν 보λμ λΉ¨κ° κ΅¬μ¬κ³Ό νλ ꡬμ¬μ νλμ© λ£μ λ€μ, λΉ¨κ° κ΅¬μ¬μ ꡬλ©μ ν΅ν΄ λΉΌλ΄λ κ²μμ΄λ€. 보λμ μΈλ‘ ν¬κΈ°λ N, κ°λ‘ ν¬κΈ°λ Mμ΄κ³ , νΈμμ 1×1ν¬κΈ°μ μΉΈμΌλ‘ λλμ΄μ Έ μλ€. κ°μ₯ λ°κΉ₯ νκ³Ό μ΄μ λͺ¨λ λ§νμ Έ μκ³ , 보λμλ ꡬλ©μ΄ νλ μλ€. λΉ¨κ° κ΅¬μ¬κ³Ό νλ ꡬμ¬μ ν¬κΈ°λ 보λμμ 1×1ν¬κΈ°μ μΉΈμ κ°λ μ±μ°λ μ¬μ΄μ¦μ΄κ³ κ°κ° νλμ© λ€μ΄κ° μλ€. κ²μμ λͺ©νλ λΉ¨κ° κ΅¬μ¬μ ꡬλ©μ ν΅ν΄μ λΉΌλ΄λ κ²μ΄λ€. μ΄λ, νλ ꡬμ¬μ΄ ꡬλ©μ λ€μ΄κ°λ©΄ μ λλ€. μ΄λ, ꡬμ¬μ μμΌλ‘ 건λ릴 μλ μκ³ , μ€λ ₯μ μ΄μ©ν΄μ μ΄λ¦¬ μ 리 κ΅΄λ €μΌ νλ€. μΌμͺ½μΌλ‘ κΈ°μΈμ΄κΈ°, μ€λ₯Έμͺ½μΌλ‘ κΈ°μΈμ΄κΈ°, μμͺ½μΌλ‘ κΈ°μΈμ΄κΈ°, μλμͺ½μΌλ‘ κΈ°μΈμ΄κΈ°μ κ°μ λ€ κ°μ§ λμ κ°κ°μ λμμμ 곡μ λμμ μμ§μΈλ€. ..
μ€λμ μ€ννΈλ§ν¬μ λ€λλ μ¬λλ€μ΄ λͺ¨μ¬μ μΆκ΅¬λ₯Ό ν΄λ³΄λ €κ³ νλ€. μΆκ΅¬λ νμΌ μ€νμ νκ³ μ무 μ°Έμλ μλλ€. μΆκ΅¬λ₯Ό νκΈ° μν΄ λͺ¨μΈ μ¬λμ μ΄ Nλͺ μ΄κ³ μ κΈ°νκ²λ Nμ μ§μμ΄λ€. μ΄μ N/2λͺ μΌλ‘ μ΄λ£¨μ΄μ§ μ€ννΈ νκ³Ό λ§ν¬ νμΌλ‘ μ¬λλ€μ λλ μΌ νλ€. BOJλ₯Ό μ΄μνλ νμ¬ λ΅κ² μ¬λμκ² λ²νΈλ₯Ό 1λΆν° NκΉμ§λ‘ λ°°μ νκ³ , λ₯λ ₯μΉλ₯Ό μ‘°μ¬νλ€. λ₯λ ₯μΉ Sijλ iλ² μ¬λκ³Ό jλ² μ¬λμ΄ κ°μ νμ μνμ λ, νμ λν΄μ§λ λ₯λ ₯μΉμ΄λ€. νμ λ₯λ ₯μΉλ νμ μν λͺ¨λ μμ λ₯λ ₯μΉ Sijμ ν©μ΄λ€. Sijλ Sjiμ λ€λ₯Ό μλ μμΌλ©°, iλ² μ¬λκ³Ό jλ² μ¬λμ΄ κ°μ νμ μνμ λ, νμ λν΄μ§λ λ₯λ ₯μΉλ Sijμ Sjiμ΄λ€. μΆκ΅¬λ₯Ό μ¬λ―Έμκ² νκΈ° μν΄μ μ€ννΈ νμ λ₯λ ₯μΉμ λ§ν¬ νμ λ₯λ ₯μΉμ μ°¨μ΄λ₯Ό μ΅μ..
Nκ°μ μλ‘ μ΄λ£¨μ΄μ§ μμ΄ A1, A2, ..., ANμ΄ μ£Όμ΄μ§λ€. μμ μ μ¬μ΄μ λΌμλ£μ μ μλ N-1κ°μ μ°μ°μκ° μ£Όμ΄μ§λ€. μ°μ°μλ λ§μ (+), λΊμ (-), κ³±μ (×), λλμ (÷)μΌλ‘λ§ μ΄λ£¨μ΄μ Έ μλ€. μμ μ μ¬μ΄μ μ°μ°μλ₯Ό νλμ© λ£μ΄μ, μμμ νλ λ§λ€ μ μλ€. μ΄λ, μ£Όμ΄μ§ μμ μμλ₯Ό λ°κΎΈλ©΄ μ λλ€. μλ₯Ό λ€μ΄, 6κ°μ μλ‘ μ΄λ£¨μ΄μ§ μμ΄μ΄ 1, 2, 3, 4, 5, 6μ΄κ³ , μ£Όμ΄μ§ μ°μ°μκ° λ§μ (+) 2κ°, λΊμ (-) 1κ°, κ³±μ (×) 1κ°, λλμ (÷) 1κ°μΈ κ²½μ°μλ μ΄ 60κ°μ§μ μμ λ§λ€ μ μλ€ μμ κ³μ°μ μ°μ°μ μ°μ μμλ₯Ό 무μνκ³ μμμλΆν° μ§νν΄μΌ νλ€. λλμ μ μ μ λλμ μΌλ‘ λͺ«λ§ μ·¨νλ€. μμλ₯Ό μμλ‘ λλ λλ μμλ‘ λ°κΎΌ λ€ λͺ«μ μ·¨νκ³ , κ·Έ λͺ«μ μμ..
μ€λλΆν° N+1μΌμ§Έ λλ λ ν΄μ¬λ₯Ό νκΈ° μν΄μ, λ¨μ NμΌ λμ μ΅λν λ§μ μλ΄μ νλ €κ³ νλ€. λ°±μ€μ΄λ λΉμμκ² μ΅λν λ§μ μλ΄μ μ‘μΌλΌκ³ λΆνμ νκ³ , λΉμλ ν루μ νλμ© μλ‘ λ€λ₯Έ μ¬λμ μλ΄μ μ‘μλμλ€. κ°κ°μ μλ΄μ μλ΄μ μλ£νλλ° κ±Έλ¦¬λ κΈ°κ° Tiμ μλ΄μ νμ λ λ°μ μ μλ κΈμ‘ Piλ‘ μ΄λ£¨μ΄μ Έ μλ€. N = 7μΈ κ²½μ°μ λ€μκ³Ό κ°μ μλ΄ μΌμ νλ₯Ό 보μ. 1μΌμ μ‘νμλ μλ΄μ μ΄ 3μΌμ΄ 걸리며, μλ΄νμ λ λ°μ μ μλ κΈμ‘μ 10μ΄λ€. 5μΌμ μ‘νμλ μλ΄μ μ΄ 2μΌμ΄ 걸리며, λ°μ μ μλ κΈμ‘μ 15μ΄λ€. μλ΄μ νλλ° νμν κΈ°κ°μ 1μΌλ³΄λ€ ν΄ μ μκΈ° λλ¬Έμ, λͺ¨λ μλ΄μ ν μλ μλ€. μλ₯Ό λ€μ΄μ 1μΌμ μλ΄μ νκ² λλ©΄, 2μΌ, 3μΌμ μλ μλ΄μ ν μ μκ²..