์ผ | ์ | ํ | ์ | ๋ชฉ | ๊ธ | ํ |
---|---|---|---|---|---|---|
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 |
- StringBuilder
- ์คํ
- ๋
- ๋ฐฐ์ด
- stream
- ์ฟ ํกDB
- ์
- ์ฟ ํกERD
- ๋ฐฑ์ค9012
- ๋ฌธ์์ด
- StringBuffer
- ๋ฐฑ์ค11053 #ํ์ด์ฌ #python
- java
- ๋ฐ์ดํฐํ์
- ๋ฐฑ์ค1874
- ๋ฐฑ์ค9093
- ํ๋ฐฉ์ฟผ๋ฆฌ
- ์คํ์์ด
- ์๋ฐ
- ์ฐ์ฐ์
- ์คํธ๋ฆผ
- ์ฐ
- Today
- Total
๋ชฉ๋ก์๊ณ ๋ฆฌ์ฆ/dp (4)
Tech Log ๐ ๏ธ
๋ณดํธ๋์ด ์๋ ๊ธ์ ๋๋ค.
![](http://i1.daumcdn.net/thumb/C150x150.fwebp.q85/?fname=https://blog.kakaocdn.net/dn/BHX1P/btruc4r2PyT/d7BpxhJLjTS7aeIhB73F31/img.png)
์ ๊ทผ๋ฐฉ๋ฒ) ๋ค์ ์ง์ ๊ด์ ์์ ๊ฐ๊ฐ ์๊น์ ๋น์ฉ์ ๊ณ์ฐํ์ฌ ์ต์ ๋น์ฉ์ ๋น๊ตํ๋ ๊ด์ ์ผ๋ก ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ์๋ค. ex) 2๋ฒ์งธ ์ง์ ํ๋์, min(์ฒซ๋ฒ์งธ์ง์ ๋นจ๊ฐ , ์ด๋ก) ์ด๋ ๊ฒ ๊ฐ๊ฐ์ ๊ฒฝ์ฐ๋ฅผ ๋น๊ตํ์ฌ ์ฌ๋ผ๊ฐ๋ ๋ฐํ ์ ๋ฐฉ์์ผ๋ก ์๊ณ ๋ฆฌ์ฆ์ ๊ตฌ์ฑํ์๋ค. ์์ค์ฝ๋ n = int(input()) d = [[0] * 3 for _ in range(n)] min_list = [[0] * 3 for _ in range(n)] for i in range(n): i1,i2,i3 = map(int,input().split()) d[i][0] = i1 d[i][1] = i2 d[i][2] = i3 for i in range(n): if i ==0: min_list[i][0] = d[0][0] min_list[i][1] =..
![](http://i1.daumcdn.net/thumb/C150x150.fwebp.q85/?fname=https://blog.kakaocdn.net/dn/TZsmM/btrtvsBszfb/BJMAKLLNsctrXvPoGJE42k/img.png)
์ ๊ทผ๋ฐฉ๋ฒ ) ๋จผ์ 3๊น์ง์ ํฉ์ ๊ทธ๋ฆฌ ์ด๋ ต์ง ์๊ธฐ์ ๋ฐฐ์ด๋ก ์ค์ ํด์ฃผ์๋ค. ๊ทธ ๋ค์ 4๋ถํฐ ํฉ๋ค์ ๋์ดํ์๋๋ฐ ์์ด 1์ด์ค๋ ๊ฒฝ์ฐ , 2๊ฐ ์ค๋๊ฒฝ์ฐ , 3์ด์ค๋ ๊ฒฝ์ฐ ์ด๋ฐ์์ผ๋ก ๊ฒฝ์ฐ๋ฅผ ๋ ๋์๋ค. 1+1+1+1 1+2+1 1+1+2 1+3 ์ด๋ ๊ฒ 1์ ๊ฒฝ์ฐ๋ง ์ดํด๋ณด๋ฉด 1 + 3์ ์๋ฏธ๋ฅผ ๊ฐ์ง๋ค๋ ๊ฒ์ ์์ ์๋ค. ์ด๋ ๊ณง 1+d[2] ๋ฅผ ์๋ฏธํ๋ฉฐ 2,3์ ๊ฒฝ ์ฐ๋ ๋์ผํ ๋ฐฉ์์ผ๋ก ๊ณ์ฐํ์๋๋ 7์ ๊ฐ์ง์๋ฅผ ์ป์ ์ ์์๋ค. ๋ฐ๋ผ์ ์ ํ์์ d[i] = d[i-1]+ d[i-2]+d[i-3] ์์ ์ ์ ์๋ค. ----------------------- n = int(input()) d = [0] * 11 d[0] = 1 d[1] = 2 d[2] = 4 for _ in range(n): k = int(inp..
![](http://i1.daumcdn.net/thumb/C150x150.fwebp.q85/?fname=https://blog.kakaocdn.net/dn/9Nfa8/btrsMWi4WMW/YmaZ7uazw1zYXJpVucIBU0/img.png)
์ ๊ทผ๋ฐฉ๋ฒ -๋ฐํ ์ ๋ฐฉ์์ผ๋ก ์งํํ์๋ค. 2 ,3 ์ผ๋ก ๋๋์ด ๋จ์ด์ง๋ ์ง ํ์ธ ํ ํ์ ์ด๋ฅผ -1 ์ ํ ๊ฒฝ์ฐ์ ๋น๊ตํด ๋ ์์ ์๋ฅผ ๋ฐฐ์ด์ ๋ฃ์ด์ฃผ์๋. n= int(input()) d= [0] * (n+1) d[1]=0 for i in range(2,n+1): if i%2 ==0 and i%3==0: d[i] = min(d[i//2]+1,d[i//3]+1) elif i%2 ==0 and i%3 !=0: d[i] = d[i//2]+1 elif i%3 ==0 and i%2 !=0: d[i] = d[i//3]+1 else: d[i] = d[i-1]+1 d[i] = min(d[i-1]+1,d[i]) print(d[i]) print(d[n])