본문 바로가기
반응형

SWE/코테137

[성실코딩 7일차] 백준 #2163 초콜릿 자르기 / 재귀, DP 처음에 문제 접했을 때는 "재귀함수 호출" 구조 풀면 되겠다 생각햇음. 그리고 풀고나서 과정들 적는데 왜 DP인지 이해갔음! 그 전에 계산했던 부분이 재사용되는 구조였음. 비슷한 문제로 피보나치 수 구하는 문제가 있음 풀이 과정 1. 재귀적으로 호출 #include using namespace std; int cnt = 0; void DividenCount(int n, int m) { if (n==1 && m==1) { // 탈출조건 return; } if (n!=1) { // 행을 나눠주기 cnt++; DividenCount(1,m); DividenCount(n-1,m); } else if(m!=1) { // 열 나눠주기 cnt++; DividenCount(n, 1); DividenCount(n, m-.. 2018. 10. 20.
[성실코딩 6일차] 백준 #9663 N-Queen N-Queens Problem 수업시간에 백트래킹으로 푸는거다 라고 배웠는데 막상 문제 풀려하니까 은근 생각해야되서 놀랫음 내가 안다고 생각하는거 = 모르는거 해본것 = 50%아는거 반복 학습 = !!!!!! #include using namespace std; int board[15][15] = {0,}; int n; int cnt = 0; int possibleR[15] = {0,}; // 행에 Queen이 있으면 int possibleC[15] = { 0, }; // 1열에 Queen이 있으면 1열에 퀸을 놓지 못함. possibleC[1]=1 // 1열에 없으면 1열에 퀸을 놓을 수 있음. possibleC[1]=0 bool checkPossible(int _r, int _c) { if (poss.. 2018. 10. 19.
[성실코딩 6일차] 백준 #9095 1,2,3 더하기 / DP ** DP 문제로 #9084 동전 문제와 유사한데 구성원소의 숫자가 1,2,3으로 정해져있고 무엇보다 다른 건 순서가 다른 건 다른 가지수로 고려하고 있다. 풀 수 있을 줄 알았는데... ㅠㅠ 규칙성을 못찾겠다,,,, 참고 코드 링크 : http://wootool.tistory.com/77?category=634571 이 분 꺼 읽는데 결론적으로 1,2,3을 사용해서3을 만드는 방법의 수,4를 만드는 방법의 수,5를 만드는 방법의 수,....숫자의 증감이 피보나치처럼 dp[n] = dp[n-1] + dp[n-2] +dp[n-3] 인 건 알겠지만근본적으로 왜 이런 결과가 나오는지 모르겠음ㅠㅠ 2018. 10. 19.
[성실코딩 6일차] 백준 #11048 이동하기 / DP 내가 아는 DP 2차원 map 문제 중에서 가장 전형적인 문제 얏호 처음으로 DP풀었당 예제 입출력 1번 풀이방법 #include using namespace std; int map[1001][1001] = { 0, }; int DP[1001][1001] = { 0, }; int dx[3] = { 0,1,1 }; //하,우하대각선,우 int dy[3] = { 1,1,0 }; int main(void) { int n, m; cin >> n >> m; for (int i = 0; i > map[i][j]; } } DP[0][0] = map[0][0]; // map n,m 모두 방문하기 for (int i = 0; i < n;.. 2018. 10. 19.
반응형

티스토리툴바