코딩/알고리즘 (67) 썸네일형 리스트형 백준 1912 연속합 #재채점으로 오답이 나신분들이 검색으로 이 글을 많이 들어오시는 것 같다. 이 해법은 테스트케이스가 추가된(17년 12월쯤..) 후에도 정답이니, 걱정마시고 참고하시면 될거 같다. #이렇게 접근 했다. 1. 숫자를 0번부터 차근차근 더해가면서 memo배열에 현재까지의 합을 기록한다. 2. 더해가다가 memo에 음수를 기록하게 되면 그 다음 부터는 합을 0으로 초기화하고 다시 더한다 3. 1~2번 작업을 끝까지 마친 후 memo의 값중 최대값을 출력한다. 이 알고리즘을 요약하면, '합이 음수가 되는 지점이 생기면 그 이전의 숫자는 모두 신경 쓰지 않는다' 이다. 최적화를 조금 해보면 memo를 사용 하지 않고 그냥 최대값만 저장하는 변수 하나만 쓰면 되고, 숫자를 더할때도 입력받으면서 바로바로 더하면 된다.. 백준 2965 캥거루 세마리 #include #include using namespace std; int main() { int a, b, c; cin >> a >> b >> c; cout 백준 11066 파일 합치기 #include #include using namespace std; int testcase; int fileSize[501]; int sum[501]; int dp[501][501]; const int intmax = 2100000000; void initData() { for (int i = 0; i < 501; i++) { fileSize[i] = 0; sum[i] = 0; for (int j = 0; j < 501; j++) { dp[i][j] = 0; } } return; } int solve(int i, int j) { if (i == j) return 0; int minResult = intmax; for (int k = 0; k < abs(i - j); k++) { minResult = m.. 백준 9251 LCS #include #include #include using namespace std; char s1_arr[1001]; char s2_arr[1001]; int memo[1001][1001]; int main() { cin >> s1_arr >> s2_arr; int s1Size = strlen(s1_arr); int s2Size = strlen(s2_arr); for (int i = 1; i 백준 1520 내리막 길 부제 : 아주 스트레스 받은 문제 #include using namespace std; int height[501][501]; int memo[501][501]; int i_length, j_length; int pX[4] = { -1, 1, 0, 0 }; int pY[4] = { 0, 0, -1, 1 }; int solve(int x, int y) { int& memoRef = memo[x][y]; if (x == i_length - 1 && y == j_length) return 1; if (memoRef =! -1) return memoRef; int i, j; memoRef = 0; for (int k = 0; k < 4; k++) { i = x + pX[k]; j = y + pY[k]; if (.. 백준 2156 포도주 시식 이 문제는 조금 의미가 있었다고 할까.. 일단 문제를 처음 보고 든 생각은 뭔 개소리지.. 였는데, 잘 보니까 계단 오르기 문제랑 비슷한거 같더라 근데, 설마 완전 같은 문제일까.. 하고 곰곰히 생각해보니 이건 계단 오르기 문제랑 다르게 '더블점프뿐만 아니라 트리플 점프도 허용하고, 마지막 계단을 밟지 않아도 돼는' 계단 오르기 문제 이더라 쿼드라점프.. 그러니까 한번에 4계단 오르는 점프도 가능하지만, 그렇게 뛸 바에는 중간에 밟는게 당연히 이득이다. 음수가 없으니까! 트리플 점프를 하는 경우는 예를 들어 99 99 1 1 99 99 이런 경우 구구(구구단 아님 ㅎ) 먹구 구구 먹구 트리플 뛰어서 구구 먹구 구구 먹구 하는게 젤 많이 마시는거니까, 이런 상황에서만 트리플점프를 쓴다. 그리고 마지막 계단.. 백준 1005 ACM Craft 처음에 이 문제의 정답률이 17%인걸 안보고 호옹 잼겠다 싶어서 그냥 푼 문제 근데 그냥 풀었더니 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 이게 DP 처음 푼 문제였는데 난 원래 C#을 좋아하는 사람이여서 C#으로 풀었더니 시간초과에 메모리 초과에.. 4번이나 틀려서 C++로 고쳤다 그리고 C++로 고쳐서 for each를 썼더니 비쥬얼스튜디오에선 잘돼던게 컴파일 에러가 뜨더라 이때 이후로 비쥬얼 스튜디오를 거르고 코드블록을 쓴다. 근데 비쥬얼 스튜디오가 편하긴 편한데..... 그냥 한번 틀리면 돼는데 굳이 불편한 코드블록 써야돼나 싶기도 하고... 고민중 이건 첨 제출한 C#코드 using System; using System.Collections.Gene.. 백준 2579 계단 오르기 진짜 이거 첨에 문제를 잘못읽어서 세번 연속으로 밟을 수 없다 를 세번 연속으로 한칸 씩 뛸 수 없다 라고 생각해서 #include #include #include using namespace std; vector stair; vector memo_canSingle; vector memo_cannotSingle; int solve(int nowStair, int prev) { bool canSingleJump = true; if (abs(nowStair - prev) == 1 ) { canSingleJump = false; } if (nowStair == 0) { return memo_canSingle[0]; } if (nowStair == 1) { if (canSingleJump) return memo.. 이전 1 ··· 5 6 7 8 9 다음
