시카로의 공부방

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결을 위한 고민 얼핏 보고 DFS를 고려했으나, 삼각형의 높이가 500개라는 걸 보고 감이 왔다. 이건 DFS로 풀면 안된다고. 만약 DFS로 풀면 어떻게 될까? 경우의 수를 따져보면, DFS로 완전탐색하는데 걸리는 횟수는 1줄일 때 1번, 2줄일때 2번, 3줄일 때 4번, 4줄일 때 8번...이런 식으로 2^(n-1)가 된다. 500줄이면 2^499= 1,636,695,303,948,071,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,00..