CS log

[๋ฐฑ์ค€/python] 4779๋ฒˆ : ์นธํ† ์–ด ์ง‘ํ•ฉ ๋ณธ๋ฌธ

CS/Algorithm

[๋ฐฑ์ค€/python] 4779๋ฒˆ : ์นธํ† ์–ด ์ง‘ํ•ฉ

sj.cath 2024. 8. 9. 17:47

๐Ÿ“๋ฌธ์ œ

https://www.acmicpc.net/problem/4779

 

์นธํ† ์–ด ์ง‘ํ•ฉ์€ 0๊ณผ 1์‚ฌ์ด์˜ ์‹ค์ˆ˜๋กœ ์ด๋ฃจ์–ด์ง„ ์ง‘ํ•ฉ์œผ๋กœ, ๊ตฌ๊ฐ„ [0, 1]์—์„œ ์‹œ์ž‘ํ•ด์„œ ๊ฐ ๊ตฌ๊ฐ„์„ 3๋“ฑ๋ถ„ํ•˜์—ฌ ๊ฐ€์šด๋ฐ ๊ตฌ๊ฐ„์„ ๋ฐ˜๋ณต์ ์œผ๋กœ ์ œ์™ธํ•˜๋Š” ๋ฐฉ์‹์œผ๋กœ ๋งŒ๋“ ๋‹ค. ์ „์ฒด ์ง‘ํ•ฉ์ด ์œ ํ•œ์ด๋ผ๊ณ  ๊ฐ€์ •ํ•˜๊ณ , ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๊ณผ์ •์„ ํ†ตํ•ด์„œ ์นธํ† ์–ด ์ง‘ํ•ฉ์˜ ๊ทผ์‚ฌ๋ฅผ ๋งŒ๋“ค์–ด๋ณด์ž.

 

1. -๊ฐ€ 3N๊ฐœ ์žˆ๋Š” ๋ฌธ์ž์—ด์—์„œ ์‹œ์ž‘ํ•œ๋‹ค.

2. ๋ฌธ์ž์—ด์„ 3๋“ฑ๋ถ„ ํ•œ ๋’ค, ๊ฐ€์šด๋ฐ ๋ฌธ์ž์—ด์„ ๊ณต๋ฐฑ์œผ๋กœ ๋ฐ”๊พผ๋‹ค. ์ด๋ ‡๊ฒŒ ํ•˜๋ฉด, ์„ (๋ฌธ์ž์—ด) 2๊ฐœ๊ฐ€ ๋‚จ๋Š”๋‹ค.

3. ์ด์ œ ๊ฐ ์„ (๋ฌธ์ž์—ด)์„ 3๋“ฑ๋ถ„ ํ•˜๊ณ , ๊ฐ€์šด๋ฐ ๋ฌธ์ž์—ด์„ ๊ณต๋ฐฑ์œผ๋กœ ๋ฐ”๊พผ๋‹ค. ์ด ๊ณผ์ •์€ ๋ชจ๋“  ์„ ์˜ ๊ธธ์ด๊ฐ€ 1์ผ๋•Œ ๊นŒ์ง€ ๊ณ„์† ํ•œ๋‹ค.

์˜ˆ๋ฅผ ๋“ค์–ด, N=3์ธ ๊ฒฝ์šฐ, ๊ธธ์ด๊ฐ€ 27์ธ ๋ฌธ์ž์—ด๋กœ ์‹œ์ž‘ํ•œ๋‹ค.

---------------------------

์—ฌ๊ธฐ์„œ ๊ฐ€์šด๋ฐ ๋ฌธ์ž์—ด์„ ๊ณต๋ฐฑ์œผ๋กœ ๋ฐ”๊พผ๋‹ค.

---------         ---------

๋‚จ์€ ๋‘ ์„ ์˜ ๊ฐ€์šด๋ฐ ๋ฌธ์ž์—ด์„ ๊ณต๋ฐฑ์œผ๋กœ ๋ฐ”๊พผ๋‹ค.

---   ---         ---   ---

ํ•œ๋ฒˆ ๋”

- -   - -         - -   - -

๋ชจ๋“  ์„ ์˜ ๊ธธ์ด๊ฐ€ 1์ด๋ฉด ๋ฉˆ์ถ˜๋‹ค. N์ด ์ฃผ์–ด์กŒ์„ ๋•Œ, ๋งˆ์ง€๋ง‰ ๊ณผ์ •์ด ๋๋‚œ ํ›„ ๊ฒฐ๊ณผ๋ฅผ ์ถœ๋ ฅํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค

 

๐Ÿ“์ž…๋ ฅ

์ž…๋ ฅ์„ ์—ฌ๋Ÿฌ ์ค„๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ๋‹ค. ๊ฐ ์ค„์— N์ด ์ฃผ์–ด์ง„๋‹ค. ํŒŒ์ผ์˜ ๋์—์„œ ์ž…๋ ฅ์„ ๋ฉˆ์ถ˜๋‹ค. N์€ 0๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™๊ณ , 12๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ •์ˆ˜์ด๋‹ค.

๐Ÿ“์ถœ๋ ฅ

์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง„ N์— ๋Œ€ํ•ด์„œ, ํ•ด๋‹นํ•˜๋Š” ์นธํ† ์–ด ์ง‘ํ•ฉ์˜ ๊ทผ์‚ฌ๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค.

 

๐Ÿ“ํ’€์ด ๋ฐฉ๋ฒ•

  • ๊ฐ€์šด๋ฐ๋ฅผ ๋ฐ˜๋ณตํ•ด์„œ ์ž๋ฅผ ์ˆ˜ ์žˆ์„ ๋•Œ๊นŒ์ง€ ์ž˜๋ผ์ค˜์•ผ ํ•˜๋‹ˆ, ์žฌ๊ท€๋ฅผ ์ด์šฉํ•˜์—ฌ ํƒ์ƒ‰.
  • "๊ฐ€์šด๋ฐ"๋Š”? 3**N ๊ฐœ๋ฅผ 3๊ฐœ๋กœ ๋‚˜๋ˆˆ ๊ฒƒ ์ค‘ ๊ฐ€์šด๋ฐ ์กฐ๊ฐ
  • n๋ฒˆ์งธ ๊ฒฐ๊ณผ๋Š” n-1๋ฒˆ์งธ ๊ฒฐ๊ณผ๋ฅผ ์ด์–ด๋ถ™์ธ ๊ฒƒ๊ณผ ๊ฐ™๋‹ค. n-1๋ฒˆ์งธ ๊ฒฐ๊ณผ ์‚ฌ์ด์— n-1๋ฒˆ์งธ ๊ฒฐ๊ณผ์˜ ๊ธธ์ด๋งŒํผ ๊ณต๋ฐฑ๋งŒ ๋„ฃ์–ด์ฃผ๋ฉด ๋œ๋‹ค. ์ฆ‰, n๋ฒˆ์งธ ๊ฒฐ๊ณผ = n-1๋ฒˆ์งธ ๊ฒฐ๊ณผ + n-1๋ฒˆ์งธ ๊ฒฐ๊ณผ ๊ธธ์ด๋งŒํผ์˜ ๊ณต๋ฐฑ + n-1๋ฒˆ์งธ ๊ฒฐ๊ณผ

 

๐Ÿ“์ฝ”๋“œ

import sys
def can(n) :
    if n == 1 :
        return "-"
    cantor_unit = can(n//3)
    cantor_res = cantor_unit + " " * (n//3) + cantor_unit
    return cantor_res

while True :
    try :
        N = int(sys.stdin.readline())
        print(can(3**N))
    except :
        break

 

๐Ÿ“์‹œ๊ฐ„๋ณต์žก๋„

 

O(3^N)

 

๐Ÿ“์žฌ๊ท€

์ด ๋ถ€๋ถ„์ด ํ•ต์‹ฌ ํฌ์ธํŠธ!

โžก๏ธ n๋ฒˆ์งธ ๊ฒฐ๊ณผ๋Š” n-1๋ฒˆ์งธ ๊ฒฐ๊ณผ๋ฅผ ์ด์–ด๋ถ™์ธ ๊ฒƒ๊ณผ ๊ฐ™๋‹ค. n-1๋ฒˆ์งธ ๊ฒฐ๊ณผ ์‚ฌ์ด์— n-1๋ฒˆ์งธ ๊ฒฐ๊ณผ์˜ ๊ธธ์ด๋งŒํผ ๊ณต๋ฐฑ๋งŒ ๋„ฃ์–ด์ฃผ๋ฉด ๋œ๋‹ค. ์ฆ‰, n๋ฒˆ์งธ ๊ฒฐ๊ณผ = n-1๋ฒˆ์งธ ๊ฒฐ๊ณผ + n-1๋ฒˆ์งธ ๊ฒฐ๊ณผ ๊ธธ์ด๋งŒํผ์˜ ๊ณต๋ฐฑ + n-1๋ฒˆ์งธ ๊ฒฐ๊ณผ

 

์žฌ๊ท€์— ๊ด€ํ•œ ํฌ์ŠคํŒ… : https://doleebest.tistory.com/78