본문 바로가기
Problem Solving/BOJ

[BOJ][Python]15489번 풀이

by NoiB 2022. 6. 4.
반응형

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

 

15489번: 파스칼 삼각형

첫째 줄에 양의 정수 R, C, W가 공백을 한 칸씩 두고 차례로 주어진다. (단, 2 ≤ R+W ≤ 30, 2 ≤ C+W ≤ 30, 1 ≤ W ≤ 29, C ≤ R)

www.acmicpc.net

t = [[0 for _ in range(31)] for _ in range(31)]
t[1][1] = 1
for i in range(2,31):
    for j in range(1,31):
        t[i][j] = t[i-1][j-1] + t[i-1][j]
r,c,w = map(int, input().split())
answer = 0
for i in range(w):
    for j in range(i+1):
        answer += t[r+i][c+j]
print(answer)

어제 풀었던 이항 계수 문제를 베이스로 깔고 거기서 원하는 원소들의 합을 구하는 게 추가된 문제입니다. 여기서 사용된 테크닉 중에서 이중 반복문을 사용할 때 j를 i만큼만 반복시키는 이 테크닉을 처음 봤을 때 정말 감탄했었는데요. 그래서 그런가 해당 테크닉을 쓸 수 있게 해주는 이 문제가 뭔가 좋은 느낌입니다.

 

해당 문제를 처음 푸시는 분들은 정삼각형이라는 말에 현혹되지 않으시길 바랍니다. 특히 알고리즘 문제를 엄청 제대로 풀려고 문장 하나 하나에 의미를 부여하다보면 스스로 만들어낸 함정에 빠지게 되거든요. 해당 문제는 정삼각형이라는 말이 전혀 중요하지 않습니다. 본인이 어떻게 인덱스를 가지고 놀 것인지, 그러기 위해서 가장 효율적인 리스트와 점화식의 형태가 어떤 것인지에만 집중하시면 간단하게 풀 수 있을겁니다.

반응형

'Problem Solving > BOJ' 카테고리의 다른 글

[BOJ][Python]14606번 풀이  (0) 2022.06.05
[BOJ][Python]11047번 풀이  (0) 2022.06.05
[BOJ][Python]17219번 풀이  (0) 2022.06.04
[BOJ][Python]16395번 풀이  (0) 2022.06.03