μΌ | μ | ν | μ | λͺ© | κΈ | ν |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 | 29 |
30 |
- κ·Έλν
- DFS
- νλ‘κ·Έλλ¨Έμ€
- db
- λ³ν©μ λ ¬
- λ°±μ€
- μ λ ¬
- μ°μ μμν
- μμꡬνκΈ°
- λ€μ΄λλ―Ήνλ‘κ·Έλλ°
- λμ κ³νλ²
- κ·Έλνμνλ¬Έμ
- μκ³ λ¦¬μ¦
- λ°μ΄ν°λ² μ΄μ€
- λ¨Έμ§μνΈ
- κΉμ΄μ°μ νμ
- κ·Έλννμ
- νλ‘μ΄λμμ¬
- LIS
- SQL
- BFS
- λλΉμ°μ νμ
- 그리λ
- μν
- Side Menu
- μμνμ
- μλ£κ΅¬μ‘°
- ꡬν
- DP
- 11650
λͺ©λ‘μ½λ©ν μ€νΈ μ€λΉ (77)
πππ°πΈ π£πΆπ΅ π΄π΅π¦π’π₯πΊ
λ¬Έμ μκ·Όμ΄λ μμ μ κ²°νΌμμ νκ΅ λκΈ° μ€ μμ μ μΉκ΅¬μ μΉκ΅¬μ μΉκ΅¬λ₯Ό μ΄λνκΈ°λ‘ νλ€. μκ·Όμ΄μ λκΈ°λ λͺ¨λ Nλͺ μ΄κ³ , μ΄ νμλ€μ νλ²μ λͺ¨λ 1λΆν° NκΉμ§μ΄λ€. μκ·Όμ΄μ νλ²μ 1μ΄λ€. μκ·Όμ΄λ λκΈ°λ€μ μΉκ΅¬ κ΄κ³λ₯Ό λͺ¨λ μ‘°μ¬ν 리μ€νΈλ₯Ό κ°μ§κ³ μλ€. μ΄ λ¦¬μ€νΈλ₯Ό λ°νμΌλ‘ κ²°νΌμμ μ΄λν μ¬λμ μλ₯Ό ꡬνλ νλ‘κ·Έλ¨μ μμ±νμμ€. μ λ ₯ 첫째 μ€μ μκ·Όμ΄μ λκΈ°μ μ n (2 ≤ n ≤ 500)μ΄ μ£Όμ΄μ§λ€. λμ§Έ μ€μλ 리μ€νΈμ κΈΈμ΄ m (1 ≤ m ≤ 10000)μ΄ μ£Όμ΄μ§λ€. λ€μ μ€λΆν° mκ° μ€μλ μΉκ΅¬ κ΄κ³ ai biκ° μ£Όμ΄μ§λ€. (1 ≤ ai < bi ≤ n) aiμ biκ° μΉκ΅¬λΌλ λ»μ΄λ©°, biμ aiλ μΉκ΅¬κ΄κ³μ΄λ€. μΆλ ₯ 첫째 μ€μ μκ·Όμ΄μ κ²°νΌμμ μ΄λνλ λκΈ°μ μλ₯Ό μΆλ ₯νλ€. κ·Έλν..
λ¬Έμ νμ€μ΄λ νλ‘κ·Έλλ° λνλ₯Ό κ°μ΅νλ€. μ΄ λνλ μ¬λλ€μ΄ νμ μ΄λ£¨μ΄μ μ°Έκ°ν΄μΌ νλ©°, νμμ μλ νμ€μ΄κ° μ ν΄μ€λ€. νμμ΄ νμ€μ΄κ° μ ν κ°λ³΄λ€ λΆμ‘±νλ€λ©΄, κ·Έ νμ λνμ μ°Έμ¬ν μ μλ€. λͺ¨λ νμ κ°μ μμ νμμΌλ‘ μ΄λ£¨μ΄μ Έ μλ€. λνμ μ°Έμ¬ μμ¬λ₯Ό λ°ν νκ΅λ μ΄ Nκ°μ΄λ€. κ° νκ΅λ λͺ¨λ νμμ΄ μ°Έμ¬ν μ μλ κ²½μ°μλ§ λνμ μ°Έκ°νλ€. μ¦, λ¨λ μ¬λ μμ΄ λͺ¨λ νμμ΄ νμ λ€μ΄κ° μ μμ΄μΌ νλ€. λνλ μμ κ³Ό λ³Έμ μΌλ‘ ꡬμ±λμ΄ μλ€. λͺ¨λ νμ κ°μ νκ΅ μμμΌλ‘ μ΄λ£¨μ΄μ Έ μμ΄μΌ νλ€. μμ μμ κ° νκ΅ 1λ±νλ§ λ³Έμ μ μ§μΆνλ€. νμ€μ΄μ λνλ μ¬ν΄κ° 첫 ν΄μ΄κΈ° λλ¬Έμ, λ§μ κ΄μ¬μ΄ νμνλ€. λ°λΌμ, λ³Έμ μ μ°Έκ°νλ μ¬λμ μλ₯Ό μ΅λκ° λλλ‘ νμμ μλ₯Ό μ νλ €κ³ νλ€. λ,..
λ¬Έμ μκ·Ό(Albert), λ―Όν(Barbara), μ μ(Casper), μ°½μ(Dinko), νμ§(Eustahije)μ΄κ° λ§λΌν€ ν±νν κ²μμ νλ €κ³ νλ€. μ΄ κ²μμ N×N 보λμμ μ§ννλ€. 맨 μ²μμ 보λμ λͺ¨λ μΉΈμ λΉμ΄μλ€. νλ μ΄μ΄λ ν΄μ λ²κ°μκ°λ©΄μ μμ μ μμ΄ μ΄λ¦μ 첫 κΈμλ₯Ό λΉ μΉΈμ μ λλ€. (λ μ¬λμ μμ΄ μ΄λ¦μ 첫 κΈμκ° κ°μ κ²½μ°λ μλ€) κ²μμ μΈ κΈμκ° ν, μ΄, λλ λκ°μ μΌλ‘ μ°μν λ, κ·Έ νλ μ΄μ΄κ° μΉλ¦¬νλ©°, κ²μμ΄ λλκ² λλ€. 보λνμ μνκ° μ£Όμ΄μ‘μ λ, κ²μμ΄ λλ¬λμ§ μλμ§λ₯Ό κ²°μ νκ³ , λλ¬λ€λ©΄ μΉμκ° λꡬμΈμ§ ꡬνλ νλ‘κ·Έλ¨μ μμ±νμμ€. μ λ ₯ 첫째 μ€μ 보λνμ ν¬κΈ° Nμ΄ μ£Όμ΄μ§λ€. (1 ≤ N ≤ 30) λ€μ Nκ° μ€μλ 보λνμ μνκ° μ£Όμ΄μ§λ€. '.'λ..
λ¬Έμ μλνΌμ μμ£Ό μ§μ μμ Nκ°μ νΌμ λ°μ£½μ μ€λΈμ λ£κ³ ꡬμ°λ €κ³ νλ€. κ·Έλ°λ°, μλνΌμμμ λ§λλ νΌμ λ°μ£½μ μ§λ¦μ΄ μ κ°κ°μ΄λ€. κ·Έλ°κ°νλ©΄, μλνΌμμμ μ¬μ©νλ μ€λΈμ λͺ¨μλ λͺΉμ μ€λ¬νλ€. μ΄ μ€λΈμ κΉμ κ΄μ²λΌ μκ²Όλλ°, κ΄μ μ§λ¦μ΄ κΉμ΄μ λ°λΌ λ€μλ μνκ² λ³νλ€. μλλ μ€λΈμ λ¨λ©΄ μμμ΄λ€. νΌμ λ°μ£½μ μμ±λλ μμλλ‘ μ€λΈμ λ€μ΄κ°λ€. μ΄λ κ² Nκ°μ νΌμκ° μ€λΈμ λͺ¨λ λ€μ΄κ°κ³ λλ©΄, 맨 μμ νΌμκ° μΌλ§λ κΉμ΄ λ€μ΄κ° μλμ§κ° κΆκΈνλ€. μ΄λ₯Ό μμλ΄λ νλ‘κ·Έλ¨μ μμ±νμμ€. μ λ ₯ 첫째 μ€μ μ€λΈμ κΉμ΄ Dμ νΌμ λ°μ£½μ κ°μ Nμ΄ κ³΅λ°±μ μ¬μ΄μ λκ³ μ£Όμ΄μ§λ€. (1 ≤ D, N ≤ 300,000) λμ§Έ μ€μλ μ€λΈμ μ΅μλ¨λΆν° μμνμ¬ κΉμ΄μ λ°λ₯Έ μ€λΈμ μ§λ¦μ΄ μ°¨λ‘λλ‘ μ£Όμ΄μ§λ€..
λ¬Έμ μλμ΄λ μ΅κ·Όμ νμ΄μ λ°ν΄λ₯Ό ꡬ맀νλ€. μλμ΄λ λ°ν΄μ κ° μΉΈμ μνλ²³ λλ¬Έμλ₯Ό μλ κ·Έλ¦Όκ³Ό κ°μ΄ μ μλ€. λ°ν΄μ κ°μ κΈμλ λ λ² μ΄μ λ±μ₯νμ§ μλλ€. λ, λ°ν΄λ μκ³λ°©ν₯μΌλ‘λ§ λμκ°λ€. λ°ν΄ μμλ νμ΄νκ° μλλ°, μ΄ νμ΄νλ νμ ν κ³³μ κ°λ¦¬ν€κ³ μμΌλ©°, λμκ°λ λμ κ°λ¦¬ν€λ κΈμλ λ°λκ² λλ€. μμ κ·Έλ¦Όμμλ Hλ₯Ό κ°λ¦¬ν€κ³ μλ€. μλμ΄λ λ°ν΄λ₯Ό μ°μν΄μ Kλ² λ릴 κ²μ΄λ€. λ§€λ² λ°ν΄λ₯Ό λ릴 λ λ§λ€, μλμ΄λ νμ΄νκ° κ°λ¦¬ν€λ κΈμκ° λ³νλ νμμ μ΄λ€ κΈμμμ νμ μ λ©μΆμλμ§λ₯Ό μ’ μ΄μ μ λλ€. ν¬μμ΄λ μλμ΄κ° μ μ΄λμ μ’ μ΄λ₯Ό λ°κ²¬νλ€. κ·Έ μ’ μ΄λ₯Ό λ°νμΌλ‘ μλμ΄κ° λ°ν΄μ μ μ μνλ²³μ μμλ΄λ €κ³ νλ€. μλμ΄κ° μ’ μ΄μ μ μ΄λμ λ΄μ©κ³Ό λ°ν΄μ μΉΈμ μκ° μ£Όμ΄μ‘μ λ, λ°ν΄..
λ¬Έμ μ μ Nκ°λ‘ μ΄λ£¨μ΄μ§ μμ΄ Aκ° μλ€. μ΄λ, iλ²μ§Έ μκ° κ·Έ μμ μλ μ μΈ κ°μ ν©μΌλ‘ λνλΌ μ μμ λ, κ·Έ μλ₯Ό μ’λ€κ³ νλ€. (κ°μ μμΉμ μλ μλ₯Ό μ¬λ¬ λ² λν΄λ λλ€) μμ΄μ΄ μ£Όμ΄μ‘μ λ, μ΄ λͺ κ°μ μκ° μ’μ μ μΌκΉ? μ λ ₯ 첫째 μ€μ μμ΄ Aμ ν¬κΈ° Nμ΄ μ£Όμ΄μ§λ€. (1 ≤ N ≤ 5000) λμ§Έ μ€μλ μμ΄ Aμ κ° μ«μκ° κ³΅λ°±μΌλ‘ ꡬλΆλμ΄ μ£Όμ΄μ§λ€. (-100,000 ≤ Ai ≤ 100,000) μΆλ ₯ 첫째 μ€μ μ’μ μμ κ°μλ₯Ό μΆλ ₯νλ€. μ€λλ§μ νμ΄λ³΄μλ λ€μ΄λλ―Ή νλ‘κ·Έλλ° λ¬Έμ μλ€. νμ΄λ³Έμ§λ μ€λλκ±°λμ, λμ΄λ μλ λ¬Έμ λΌ μ€μ€λ‘ μκ°ν΄λ΄κΈ°κ° λ무 μ΄λ €μμ κ²°κ΅ κ΅¬κΈμ νμ λΉλ Έλ€γ γ ν΅μ¬μ μΈ μμ x + y + z = n μ΄λ―λ‘, μ 리νλ©΄ x + y = n - ..
λ¬Έμ μ΄μ§ νΈλ¦¬λ₯Ό μ λ ₯λ°μ μ μ μν(preorder traversal), μ€μ μν(inorder traversal), νμ μν(postorder traversal)ν κ²°κ³Όλ₯Ό μΆλ ₯νλ νλ‘κ·Έλ¨μ μμ±νμμ€. μλ₯Ό λ€μ΄ μμ κ°μ μ΄μ§ νΈλ¦¬κ° μ λ ₯λλ©΄, μ μ μνν κ²°κ³Ό : ABDCEFG // (루νΈ) (μΌμͺ½ μμ) (μ€λ₯Έμͺ½ μμ) μ€μ μνν κ²°κ³Ό : DBAECFG // (μΌμͺ½ μμ) (루νΈ) (μ€λ₯Έμͺ½ μμ) νμ μνν κ²°κ³Ό : DBEGFCA // (μΌμͺ½ μμ) (μ€λ₯Έμͺ½ μμ) (루νΈ) κ° λλ€. μ λ ₯ 첫째 μ€μλ μ΄μ§ νΈλ¦¬μ λ Έλμ κ°μ N(1 ≤ N ≤ 26)μ΄ μ£Όμ΄μ§λ€. λμ§Έ μ€λΆν° Nκ°μ μ€μ κ±Έμ³ κ° λ Έλμ κ·Έμ μΌμͺ½ μμ λ Έλ, μ€λ₯Έμͺ½ μμ λ Έλκ° μ£Όμ΄μ§λ€. λ Έλμ μ΄λ¦μ AλΆν° μ°¨λ‘λλ‘..
λ¬Έμ N×Mν¬κΈ°μ λ°°μ΄λ‘ ννλλ λ―Έλ‘κ° μλ€. 1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 1 λ―Έλ‘μμ 1μ μ΄λν μ μλ μΉΈμ λνλ΄κ³ , 0μ μ΄λν μ μλ μΉΈμ λνλΈλ€. μ΄λ¬ν λ―Έλ‘κ° μ£Όμ΄μ‘μ λ, (1, 1)μμ μΆλ°νμ¬ (N, M)μ μμΉλ‘ μ΄λν λ μ§λμΌ νλ μ΅μμ μΉΈ μλ₯Ό ꡬνλ νλ‘κ·Έλ¨μ μμ±νμμ€. ν μΉΈμμ λ€λ₯Έ μΉΈμΌλ‘ μ΄λν λ, μλ‘ μΈμ ν μΉΈμΌλ‘λ§ μ΄λν μ μλ€. μμ μμμλ 15μΉΈμ μ§λμΌ (N, M)μ μμΉλ‘ μ΄λν μ μλ€. μΉΈμ μ λμλ μμ μμΉμ λμ°© μμΉλ ν¬ν¨νλ€. μ λ ₯ 첫째 μ€μ λ μ μ N, M(2 ≤ N, M ≤ 100)μ΄ μ£Όμ΄μ§λ€. λ€μ Nκ°μ μ€μλ Mκ°μ μ μλ‘ λ―Έλ‘κ° μ£Όμ΄μ§λ€. κ°κ°μ μλ€μ λΆμ΄μ μ λ ₯..
λ¬Έμ μ² μμ ν λ§ν λμ₯μμλ ν λ§ν λ₯Ό 보κ΄νλ ν° μ°½κ³ λ₯Ό κ°μ§κ³ μλ€. ν λ§ν λ μλμ κ·Έλ¦Όκ³Ό κ°μ΄ 격μ λͺ¨μ μμμ μΉΈμ νλμ© λ£μ΄μ μ°½κ³ μ 보κ΄νλ€. μ°½κ³ μ 보κ΄λλ ν λ§ν λ€ μ€μλ μ μ΅μ κ²λ μμ§λ§, μμ§ μ΅μ§ μμ ν λ§ν λ€λ μμ μ μλ€. λ³΄κ΄ ν νλ£¨κ° μ§λλ©΄, μ΅μ ν λ§ν λ€μ μΈμ ν κ³³μ μλ μ΅μ§ μμ ν λ§ν λ€μ μ΅μ ν λ§ν μ μν₯μ λ°μ μ΅κ² λλ€. νλμ ν λ§ν μ μΈμ ν κ³³μ μΌμͺ½, μ€λ₯Έμͺ½, μ, λ€ λ€ λ°©ν₯μ μλ ν λ§ν λ₯Ό μλ―Ένλ€. λκ°μ λ°©ν₯μ μλ ν λ§ν λ€μκ²λ μν₯μ μ£Όμ§ λͺ»νλ©°, ν λ§ν κ° νΌμ μ μ λ‘ μ΅λ κ²½μ°λ μλ€κ³ κ°μ νλ€. μ² μλ μ°½κ³ μ 보κ΄λ ν λ§ν λ€μ΄ λ©°μΉ μ΄ μ§λλ©΄ λ€ μ΅κ² λλμ§, κ·Έ μ΅μ μΌμλ₯Ό μκ³ μΆμ΄ νλ€. ν λ§ν λ₯Ό μ°½κ³ μ 보κ΄νλ 격μλͺ¨μμ μμλ€..
λ¬Έμ μ μ¬κ°νμΌλ‘ μ΄λ£¨μ΄μ Έ μλ μ¬κ³Ό λ°λ€ μ§λκ° μ£Όμ΄μ§λ€. μ¬μ κ°μλ₯Ό μΈλ νλ‘κ·Έλ¨μ μμ±νμμ€. ν μ μ¬κ°νκ³Ό κ°λ‘, μΈλ‘ λλ λκ°μ μΌλ‘ μ°κ²°λμ΄ μλ μ¬κ°νμ κ±Έμ΄κ° μ μλ μ¬κ°νμ΄λ€. λ μ μ¬κ°νμ΄ κ°μ μ¬μ μμΌλ €λ©΄, ν μ μ¬κ°νμμ λ€λ₯Έ μ μ¬κ°νμΌλ‘ κ±Έμ΄μ κ° μ μλ κ²½λ‘κ° μμ΄μΌ νλ€. μ§λλ λ°λ€λ‘ λλ¬μΈμ¬ μμΌλ©°, μ§λ λ°μΌλ‘ λκ° μ μλ€. μ λ ₯ μ λ ₯μ μ¬λ¬ κ°μ ν μ€νΈ μΌμ΄μ€λ‘ μ΄λ£¨μ΄μ Έ μλ€. κ° ν μ€νΈ μΌμ΄μ€μ 첫째 μ€μλ μ§λμ λλΉ wμ λμ΄ hκ° μ£Όμ΄μ§λ€. wμ hλ 50λ³΄λ€ μκ±°λ κ°μ μμ μ μμ΄λ€. λμ§Έ μ€λΆν° hκ° μ€μλ μ§λκ° μ£Όμ΄μ§λ€. 1μ λ , 0μ λ°λ€μ΄λ€. μ λ ₯μ λ§μ§λ§ μ€μλ 0μ΄ λ κ° μ£Όμ΄μ§λ€. μΆλ ₯ κ° ν μ€νΈ μΌμ΄μ€μ λν΄μ, μ¬μ κ°μλ₯Ό μΆλ ₯νλ€..