λͺ©λ‘π¦₯ μ½ν /BAEKJOON (287)
π 곡λΆνλ μ§μ§μνμΉ΄λ μ²μμ΄μ§?
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/22e5q/btspeHBNWGi/teE383wcYwfhjBHnmZkgr0/img.png)
μ μλ₯Ό μ μ₯νλ μ€νμ ꡬνν λ€μ, μ λ ₯μΌλ‘ μ£Όμ΄μ§λ λͺ λ Ήμ μ²λ¦¬νλ νλ‘κ·Έλ¨μ μμ±νμμ€. λͺ λ Ήμ μ΄ λ€μ― κ°μ§μ΄λ€. push X: μ μ Xλ₯Ό μ€νμ λ£λ μ°μ°μ΄λ€. pop: μ€νμμ κ°μ₯ μμ μλ μ μλ₯Ό λΉΌκ³ , κ·Έ μλ₯Ό μΆλ ₯νλ€. λ§μ½ μ€νμ λ€μ΄μλ μ μκ° μλ κ²½μ°μλ -1μ μΆλ ₯νλ€. size: μ€νμ λ€μ΄μλ μ μμ κ°μλ₯Ό μΆλ ₯νλ€. empty: μ€νμ΄ λΉμ΄μμΌλ©΄ 1, μλλ©΄ 0μ μΆλ ₯νλ€. top: μ€νμ κ°μ₯ μμ μλ μ μλ₯Ό μΆλ ₯νλ€. λ§μ½ μ€νμ λ€μ΄μλ μ μκ° μλ κ²½μ°μλ -1μ μΆλ ₯νλ€. μ λ ₯ 첫째 μ€μ μ£Όμ΄μ§λ λͺ λ Ήμ μ N (1 ≤ N ≤ 10,000)μ΄ μ£Όμ΄μ§λ€. λμ§Έ μ€λΆν° Nκ°μ μ€μλ λͺ λ Ήμ΄ νλμ© μ£Όμ΄μ§λ€. μ£Όμ΄μ§λ μ μλ 1λ³΄λ€ ν¬κ±°λ κ°κ³ , 100,000λ³΄λ€ μ..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/b6lYJI/btspepOMFdJ/Ykp6P81oZfNzQNMG9SBvR1/img.png)
μλ μμ μ μνμ΄ νμ ν° κ³¨μΉ«κ±°λ¦¬μλ λλΌκ° μμλ€. μ΄ λλΌμ κ΅μ κΉμ§λ―Όμ λ€μκ³Ό κ°μ λ¬Έμ λ₯Ό λ΄κ³ ν° μκΈμ κ±Έμλ€. κΈΈμ΄κ° NμΈ μ μ λ°°μ΄ Aμ Bκ° μλ€. λ€μκ³Ό κ°μ΄ ν¨μ Sλ₯Ό μ μνμ. S = A[0] × B[0] + ... + A[N-1] × B[N-1] Sμ κ°μ κ°μ₯ μκ² λ§λ€κΈ° μν΄ Aμ μλ₯Ό μ¬λ°°μ΄νμ. λ¨, Bμ μλ μλ μ¬λ°°μ΄νλ©΄ μ λλ€. Sμ μ΅μκ°μ μΆλ ₯νλ νλ‘κ·Έλ¨μ μμ±νμμ€. μ λ ₯ 첫째 μ€μ Nμ΄ μ£Όμ΄μ§λ€. λμ§Έ μ€μλ Aμ μλ Nκ°μ μκ° μμλλ‘ μ£Όμ΄μ§κ³ , μ μ§Έ μ€μλ Bμ μλ μκ° μμλλ‘ μ£Όμ΄μ§λ€. Nμ 50λ³΄λ€ μκ±°λ κ°μ μμ°μμ΄κ³ , Aμ Bμ κ° μμλ 100λ³΄λ€ μκ±°λ κ°μ μμ΄ μλ μ μμ΄λ€ μΆλ ₯ 첫째 μ€μ Sμ μ΅μκ°μ μΆλ ₯νλ€. // [10..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/lTNJb/btspdJz5Ll1/BePYdkoHv9Wbm74S7jTvW1/img.png)
Nκ°μ μ μκ° μ£Όμ΄μ§λ€. μ΄λ, Nκ°μ μ μλ₯Ό μ€λ¦μ°¨μμΌλ‘ μ λ ¬νλ νλ‘κ·Έλ¨μ μμ±νμμ€. κ°μ μ μλ ν λ²λ§ μΆλ ₯νλ€. μ λ ₯ 첫째 μ€μ μμ κ°μ N (1 ≤ N ≤ 100,000)μ΄ μ£Όμ΄μ§λ€. λμ§Έμλ μ«μκ° μ£Όμ΄μ§λ€. μ΄ μλ μ λκ°μ΄ 1,000λ³΄λ€ μκ±°λ κ°μ μ μμ΄λ€. μΆλ ₯ 첫째 μ€μ μλ₯Ό μ€λ¦μ°¨μμΌλ‘ μ λ ¬ν κ²°κ³Όλ₯Ό μΆλ ₯νλ€. μ΄λ, κ°μ μλ ν λ²λ§ μΆλ ₯νλ€. // [10867] μ€λ³΅ λΉΌκ³ μ λ ¬νκΈ° /* Nκ°μ μ μκ° μ£Όμ΄μ§λ€. μ΄λ, Nκ°μ μ μλ₯Ό μ€λ¦μ°¨μμΌλ‘ μ λ ¬νλ νλ‘κ·Έλ¨μ μμ±νμμ€. κ°μ μ μλ ν λ²λ§ μΆλ ₯νλ€. μ λ ₯ 첫째 μ€μ μμ κ°μ N (1 ≤ N ≤ 100,000)μ΄ μ£Όμ΄μ§λ€. λμ§Έμλ μ«μκ° μ£Όμ΄μ§λ€. μ΄ μλ μ λκ°μ΄ 1,000λ³΄λ€ μκ±°λ κ°μ μ μμ΄λ€. μΆλ ₯ 첫째..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/bx244Y/btso22tJJbu/CyOSCGGOIKt0OPFuHvtAzK/img.png)
μνλ²³ μλ¬Έμλ‘ μ΄λ£¨μ΄μ§ Nκ°μ λ¨μ΄κ° λ€μ΄μ€λ©΄ μλμ κ°μ 쑰건μ λ°λΌ μ λ ¬νλ νλ‘κ·Έλ¨ κΈΈμ΄κ° 짧μ κ²λΆν° κΈΈμ΄κ° κ°μΌλ©΄ μ¬μ μμΌλ‘ λ¨, μ€λ³΅λ λ¨μ΄λ νλλ§ λ¨κΈ°κ³ μ κ±°ν΄μΌ νλ€. μ λ ₯ 첫째 μ€μ λ¨μ΄μ κ°μ Nμ΄ μ£Όμ΄μ§λ€. (1 ≤ N ≤ 20,000) λμ§Έ μ€λΆν° Nκ°μ μ€μ κ±Έμ³ μνλ²³ μλ¬Έμλ‘ μ΄λ£¨μ΄μ§ λ¨μ΄κ° ν μ€μ νλμ© μ£Όμ΄μ§λ€. μ£Όμ΄μ§λ λ¬Έμμ΄μ κΈΈμ΄λ 50μ λμ§ μλλ€. μΆλ ₯ 쑰건μ λ°λΌ μ λ ¬νμ¬ λ¨μ΄λ€μ μΆλ ₯νλ€. // [1181] λ¨μ΄ μ λ ¬ /* μνλ²³ μλ¬Έμλ‘ μ΄λ£¨μ΄μ§ Nκ°μ λ¨μ΄κ° λ€μ΄μ€λ©΄ μλμ κ°μ 쑰건μ λ°λΌ μ λ ¬νλ νλ‘κ·Έλ¨ κΈΈμ΄κ° 짧μ κ²λΆν° κΈΈμ΄κ° κ°μΌλ©΄ μ¬μ μμΌλ‘ λ¨, μ€λ³΅λ λ¨μ΄λ νλλ§ λ¨κΈ°κ³ μ κ±°ν΄μΌ νλ€. μ λ ₯ 첫째 μ€μ λ¨μ΄μ κ°μ Nμ΄ μ£Όμ΄μ§λ€. ..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/dHgn0M/btso5YdovbR/OLWzc2kXXiF2XHCckWxCt0/img.png)
μΈ λκ°μ μ΄ ν μ μμ λ§λμ§ μλ λ³Όλ‘ Nκ°νμ΄ μ£Όμ΄μ‘μ λ, λκ°μ μ κ΅μ°¨μ μ κ°μλ₯Ό μΈλ νλ‘κ·Έλ¨μ μμ±νμμ€. μλ κ·Έλ¦Όμ μμ 쑰건μ λ§μ‘±νλ ν μ‘κ°νμ κ΅μ°¨μ κ·Έλ¦Όμ΄λ€. λͺ¨λ λ΄λΆκ°μ΄ 180λλ³΄λ€ μμ λ€κ°νμ λ³Όλ‘ λ€κ°νμ΄λΌκ³ νλ€. μ λ ₯ 첫째 μ€μ Nμ΄ μ£Όμ΄μ§λ€. (3 ≤ N ≤ 100) μΆλ ₯ 첫째 μ€μ κ΅μ°¨μ μ κ°μλ₯Ό μΆλ ₯νλ€. // [3049] λ€κ°νμ λκ°μ λ€κ΅μ΄ /* μΈ λκ°μ μ΄ ν μ μμ λ§λμ§ μλ λ³Όλ‘ Nκ°νμ΄ μ£Όμ΄μ‘μ λ, λκ°μ μ κ΅μ°¨μ μ κ°μλ₯Ό μΈλ νλ‘κ·Έλ¨μ μμ±νμμ€. μλ κ·Έλ¦Όμ μμ 쑰건μ λ§μ‘±νλ ν μ‘κ°νμ κ΅μ°¨μ κ·Έλ¦Όμ΄λ€. λͺ¨λ λ΄λΆκ°μ΄ 180λλ³΄λ€ μμ λ€κ°νμ λ³Όλ‘ λ€κ°νμ΄λΌκ³ νλ€. μ λ ₯ 첫째 μ€μ Nμ΄ μ£Όμ΄μ§λ€. (3 ≤ N ≤ 100) μΆλ ₯ 첫째 ..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/euoicc/btsoU8Ay5pM/LKwoFbCPcZyYNvYxDdHvRk/img.png)
μ¬λ μ리μ μμ μ μκ° μ£Όμ΄μ§ λ, κ·Έ μμμ μ°μνμ¬ κ°μ μ«μκ° λμ€λ κ²μ΄ μμΌλ©΄ 1μ μΆλ ₯νκ³ , μμΌλ©΄ κ°μ μ«μκ° μ°μν΄μ λμ€λ κ΅¬κ° μ€ κ°μ₯ κΈ΄ κ²μ κΈΈμ΄λ₯Ό μΆλ ₯νλ νλ‘κ·Έλ¨μ μμ±νλΌ. μλ₯Ό λ€μ΄ μΈ κ°μ μ«μ 12345123, 17772345, 22233331μ΄ μ£Όμ΄μ‘λ€κ³ νμ. 12345123μ μ°μνμ¬ κ°μ μ«μκ° λμ€λ κ²μ΄ μμΌλ―λ‘ 1μ μΆλ ₯νκ³ , 17772345λ 7μ΄ μΈ κ° μ°μνμ¬ λμ€λ―λ‘ 3μ μΆλ ₯νλ©°, 22233331μ κ²½μ°μλ 2κ° μΈ κ°, 3μ΄ λ€ κ° μ°μν΄μ λμ€λ―λ‘ κ·Έ μ€ ν° κ°μΈ 4λ₯Ό μΆλ ₯ μ λ ₯ 첫째 μ€λΆν° μ μ§Έ μ€κΉμ§ κ° μ€μ νλμ© μΈ κ°μ μ¬λ μ리 μμ μ μκ° μ£Όμ΄μ§λ€. μΆλ ₯ 첫째 μ€μμ μ μ§Έ μ€κΉμ§ ν μ€μ νλμ© κ° μ λ ₯λ μ λ΄μμ κ°μ μ«μκ° μ°μ..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/cIzH6g/btso0OUY2Oq/gJoFiDhqfdEcv8CJbxjQS0/img.png)
1μμλΆν° 6κΉμ§μ λμ κ°μ§ 4κ°μ μ£Όμ¬μλ₯Ό λμ Έμ λ€μκ³Ό κ°μ κ·μΉμ λ°λΌ μκΈμ λ°λ κ²μμ΄ μλ€. κ°μ λμ΄ 4κ°κ° λμ€λ©΄ 50,000μ+(κ°μ λ)×5,000μμ μκΈμ λ°κ² λλ€. κ°μ λμ΄ 3κ°λ§ λμ€λ©΄ 10,000μ+(3κ°κ° λμ¨ λ)×1,000μμ μκΈμ λ°κ² λλ€. κ°μ λμ΄ 2κ°μ© λ μμ΄ λμ€λ κ²½μ°μλ 2,000μ+(2κ°κ° λμ¨ λ)×500μ+(λ λ€λ₯Έ 2κ°κ° λμ¨ λ)×500μμ μκΈμ λ°κ² λλ€. κ°μ λμ΄ 2κ°λ§ λμ€λ κ²½μ°μλ 1,000μ+(κ°μ λ)×100μμ μκΈμ λ°κ² λλ€. λͺ¨λ λ€λ₯Έ λμ΄ λμ€λ κ²½μ°μλ (κ·Έ μ€ κ°μ₯ ν° λ)×100μμ μκΈμ λ°κ² λλ€. μλ₯Ό λ€μ΄, 4κ°μ λμ΄ 3, 3, 3, 3μΌλ‘ μ£Όμ΄μ§λ©΄ 50,000+3×5,000μΌλ‘ κ³μ°λμ΄ 65,000μ..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/b8Eipf/btsoZcvmLXn/TzlFVqBkLcJ6naBoBdCng0/img.png)
λ μ¬λ Aμ Bλ 1λΆν° 10κΉμ§μ μ«μκ° νλμ© μ ν μ΄ μ₯μ μΉ΄λλ‘ ‘κ²μ’μ νλ€. κ²μμ μ΄ μ΄ λ²μ‘λΌμ΄λ’λ‘ κ΅¬μ±λκ³ , κ° λΌμ΄λ λ§λ€ μμ μ΄ κ°μ§κ³ μλ μΉ΄λ μ€ νλλ₯Ό μ μνκ³ , ν λ² μ μν μΉ΄λλ λ²λ¦°λ€. κ²μ μΉν¨λ λ€μκ³Ό κ°μ΄ κ²°μ λλ€. κ° λΌμ΄λλ λ λμ μ«μλ₯Ό μ μν μ¬λμ΄ μΉλ¦¬νκ³ , μ μν μ«μκ° κ°μ κ²½μ°λ λΉκΈ΄λ€. μ΄ λ²μ λΌμ΄λμμ λ λ§μ λΌμ΄λλ₯Ό μΉλ¦¬ν μ¬λμ΄ κ²μμ μΉλ¦¬νκ³ , μΉλ¦¬ν λΌμ΄λ νμκ° λμΌν κ²½μ° λΉκΈ΄λ€. λ€μμ κ²μμ ν μλ‘, κ° λΌμ΄λλ§λ€ Aμ Bκ° μ μν μΉ΄λμ μ«μμ κ° λΌμ΄λμ μΉμλ₯Ό 보μ¬μ€λ€. (λΉκΈ΄ λΌμ΄λλ Dλ‘ νμν¨) λΌμ΄λ 1 2 3 4 5 6 7 8 9 10 Aμ μΉ΄λ 6 7 5 1 4 10 2 3 8 9 Bμ μΉ΄λ 1 10 2 ..