dp_1. 네트워크 선 자르기
느낀점 21년 10월 4일 - for문
-
근복적으로 문제를 보자마자 어떻게 풀지 감이 안온다.
-> 이거 일일이 노가다 해볼까? 라는 생각이 들 정도로
-
입력이 7인데 출력을 21 이 나오는 것을 통해 7을 1,2로
일일이 잘라서 확인하기에는 어렵다. 21번 확인을 해야하므로
-> 이러한 상황에서 진짜 딱 직관적으로 번뜩여야 한다!
=> 프로그래밍적으로 생각하면 안되.
일단 생각해야 한다.
예시에 있는 5가지 예시에도 꽂히면 안된다..
작은 단위로 해볼까? 생각이 안날게 뻔하지만..
네트워크 선이 1일 때는 1로 자를 수 있다. -> 1개
네트워크 선이 2일 때는 1 + 1 / 2로 자를 수 있다. -> 2개
네트워크 선이 3일 때는 1 + 1 + 1 / 1 + 2 / 2 + 1 -> 3개
네트워크 선이 4일 때는 1 + 1 + 1 + 1 / 1 + 1 + 2 / 1 + 2 + 1 / 2 + 1 + 1
// 2 + 2 -> 총 5개
해보니까 규칙을 발견했다...
재귀 사용할때
근복적으로 문제를 보자마자 어떻게 풀지 감이 안온다.
-> 이거 일일이 노가다 해볼까? 라는 생각이 들 정도로
입력이 7인데 출력을 21 이 나오는 것을 통해 7을 1,2로
일일이 잘라서 확인하기에는 어렵다. 21번 확인을 해야하므로
-> 이러한 상황에서 진짜 딱 직관적으로 번뜩여야 한다!
=> 프로그래밍적으로 생각하면 안되.
일단 생각해야 한다.
예시에 있는 5가지 예시에도 꽂히면 안된다..
작은 단위로 해볼까? 생각이 안날게 뻔하지만..
네트워크 선이 1일 때는 1로 자를 수 있다. -> 1개
네트워크 선이 2일 때는 1 + 1 / 2로 자를 수 있다. -> 2개
네트워크 선이 3일 때는 1 + 1 + 1 / 1 + 2 / 2 + 1 -> 3개
네트워크 선이 4일 때는 1 + 1 + 1 + 1 / 1 + 1 + 2 / 1 + 2 + 1 / 2 + 1 + 1
// 2 + 2 -> 총 5개
해보니까 규칙을 발견했다...
- 일단 그림을 그려보면 이렇게 된다. 전형적인 복귀하면서 카운팅 되는 dfs문제.
- 주의할 점은 어디서 카운팅을 할 것인가이다.
그림을 보면 카운팅이 어디서 진행해야 올바른지 알 수 있다. - 추가적으로 재귀 진행할 때 예외처리에 주의하자. 네트워크 선을 음수로 만들 수 없다는 사실에 유의하자!
풀이전략
-
재귀 사용
-> 끄적여보면 재귀를 사용하면 될것 같았음.
-
dp 사용
: 어떻게 작성해야 할지 모를때는 경우의 수를 만들어보자.
재귀 사용
-> 끄적여보면 재귀를 사용하면 될것 같았음.
dp 사용
: 어떻게 작성해야 할지 모를때는 경우의 수를 만들어보자.
-> 점화식을 만들 수 있따.
d[3] = d[1] + d[2];
d[4] = d[3] + d[2];
소스코드
- 재귀
void recur(int n, int&cnt)
{
if (n == 0)
{
cnt++;
return;
}
if(n - 1 >= 0)
recur(n - 1, cnt);
if (n - 2 >= 0)
recur(n - 2, cnt);
}
int main(void)
{
_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
int n;
cin >> n;
int cnt = 0;
recur(n, cnt);
cout << cnt;
return 0;
}
- dp;
int main(void)
{
_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
int n;
cin >> n;
int cnt = 0;
vector<int>dp(n);
dp[0] = 1;
dp[1] = 2;
for (int i = 2; i < n; i++)
{
dp[i] = dp[i - 1] + dp[i - 2];
}
cout << dp[n -1];
return 0;
}
Author And Source
이 문제에 관하여(dp_1. 네트워크 선 자르기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@kwt0124/dp1.-네트워크-선-자르기
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
void recur(int n, int&cnt)
{
if (n == 0)
{
cnt++;
return;
}
if(n - 1 >= 0)
recur(n - 1, cnt);
if (n - 2 >= 0)
recur(n - 2, cnt);
}
int main(void)
{
_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
int n;
cin >> n;
int cnt = 0;
recur(n, cnt);
cout << cnt;
return 0;
}
int main(void)
{
_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
int n;
cin >> n;
int cnt = 0;
vector<int>dp(n);
dp[0] = 1;
dp[1] = 2;
for (int i = 2; i < n; i++)
{
dp[i] = dp[i - 1] + dp[i - 2];
}
cout << dp[n -1];
return 0;
}
Author And Source
이 문제에 관하여(dp_1. 네트워크 선 자르기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kwt0124/dp1.-네트워크-선-자르기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)