전체 글
2096번-내려가기
문제 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 접근방법 1) 접근 사고 모두 입력받아서 갱신할 필요없이 값을 입력받은 뒤에 받은 순간마다 판단해주면 되는 문제입니다. 2) 시간 복잡도 3) 배운 점 4) PS 정답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 #incl..
2225-합분해
문제 https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 접근방법 1) 접근 사고 n의 개수가 200으로 한정되있고 시간은 2초라 각각의 경우를 전부 탐색하는 형식의 완전제곱 탐색을 할 경우 시간초과가 발생함 2) 시간 복잡도 O(n^3) 3) 배운 점 배열의 각각의 위치 인덱스에 의미를 부여해서 값을 찾는 형식의 점화식을 세웠다. 4) PS 정답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 #include #define ..
17069번-파이프 옮기기2
문제 https://www.acmicpc.net/problem/17069 17069번: 파이프 옮기기 2 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 접근방법 1) 접근 사고 이 문제는 파이프를 둘 수 있는 경우에 대한 재귀와 각 조건에 대한 칸을 확인해보면서 재귀함수를 진행하면 되는 문제입니다. 2) 시간 복잡도 다이나믹 프로그래밍으로 접근 및 메모리제이션을 활용하여 O(nlogn) 3) 배운 점 DP + 간단한 구현 알고리즘 문제인거 같다. 4) PS 정답 코드 1 2 3 4 5 6 7 8 9 10 11 12 ..