알고리즘/문제풀이 - 백준

백준 1022 소용돌이 예쁘게 출력하기

문제 : https://www.acmicpc.net/problem/1022 서론 처음엔 소용돌이 전체를 배열에 저장한 후 출력하려 했으나 소용돌이 배열만 400MB로 메모리 초과가 발생했다. 그래서 소용돌이전체 중 출력을 해야하는 부분만 배열에 저장하기로했다. 쉽게 봤으나 반례찾기 등 시행착오를 상당히 많이 거친 문제. 구현 전에 확실히 가능성검토를 해야 시간을 아낄 수 있다. 아이디어 소용돌이는 규칙성이 있다. 수 1 2 3 4 5 6 7 8 9 회전방향 오른쪽 위쪽 왼쪽 아래쪽 오른쪽 위쪽 왼쪽 아래쪽 오른쪽 이동칸 1 1 2 2 3 3 4 4 5 1을 시작으로 오른쪽으로 1칸 전진한 2 2를 시작으로 위쪽으로 1칸 전진한 3 3을 시작으로 왼쪽으로 2칸 전진한 5 5를 시작으로 아래로 2칸 전진한 ..

2019. 5. 27. 22:53
알고리즘/문제풀이 - 백준

백준 9461 파도반 수열

문제 : https://www.acmicpc.net/problem/9461 풀이 점화식을 세우는것이 중요하다. n1 n2 n3 n4 n5 n6 n7 n8 n9 n10 1 1 1 2 2 3 4 5 7 9 n6부터 n[i] = n[i-5] + n[i-1]의 규칙을 발견할 수 있다. 즉 n6 = n1 + n5 구현 배열에 integer 범위를 초과하는 값이 들어가므로 더 큰 자료형을 선언해야한다. // C++ #include using namespace std; int t, n; long long dp[101]; void cal() { dp[1] = 1; dp[2] = 1; dp[3] = 1; dp[4] = 2; dp[5] = 2; for (int i = 6; i > t; for (int i = 0; i < ..

2019. 5. 23. 19:19
알고리즘/문제풀이 - 백준

백준 1912 연속합

문제 : https://www.acmicpc.net/problem/1912 서론 https://hydroponicglass.tistory.com/4 위와 같은 아이디어는 배열이 너무 커서 선언이 되질 않았다. 그래서 이중 for문으로 풀어봤으나 시간초과 결과적으로 DP를 이용한 단일 for문으로 풀어야 하는 문제였다. 풀이 예제 1 2 3 4 5 6 7 8 9 10 10 -4 3 1 5 6 -35 12 21 -1 sum[6]은 1번부터 6번까지의 합인 21이 저장되어있음 sum[6]은 sum[5]보다 큰 수이므로 결과값은 16에서 21로 갱신 sum[7]은 -14로 음수이므로 sum[7]은 0으로 갱신 (음수를 더해줄 시 최대값과 멀어짐) sum[8]은 sum[7]이 0이므로 부분합을 0부터 다시 시작함..

2019. 5. 22. 20:44