백준문제풀이
14503번-로봇청소기
문제 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 접근방법 1) 접근 사고 DFS 문제로 생각하여 DFS를 활용해서 문제를 풀었습니다. 문제의 구현량은 간단하나 DFS의 이해도가 높지 않다면 어려움을 겪을수 있는 문제입니다. 문제 에서 깊이우선탐색을 활용한 응용하는 부분이 들어있습니다. 보통 DFS는 최하단으로 내려간뒤 가지를 치면서 탐색을 하는데 이 문제의 경우 가지를 치는 방식이 기존 코드와 다르게 한 개의 시작점 부터만 가지치기가 됩..
14502번-연구소
문제 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 접근방법 1) 접근 사고 DFS + BFS 문제 였습니다. 알고리즘 과정은 1.입력값을 받고 난 board 배열에서 3개의 기둥을 설치한 뒤 2.바이러스들이 모두 퍼집니다.(BFS 알고리즘 활용) 3.이후에 남은 공간을 측정하여 최대값일 경우 갱신합니다. 4.이때 DFS를 통해서 모든 경우를 구해주면 됩니다. 2) 시간 복잡도 모든 경우를 탐색해야 하므로 O(n^2)입니다. 3) 배운 점 무난했던 구현 ..
14501번-퇴사
문제 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 접근방법 1) 접근 사고 상담을 할 것인지 안 할 것인지 두 개의 경우를 비교해주면 되는 문제였습니다. 구현 논리는 주석으로 자세하게 참조하였습니다. 2) 시간 복잡도 DP를 활용하여 O(logn)으로 해결이 가능합니다. 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 #include #defin..
14500번-테트로미노
문제 https://www.acmicpc.net/status?user_id=skaguq4270&problem_id=14500&from_mine=1 채점 현황 www.acmicpc.net 접근방법 1) 접근 사고 문제에 보면 한 테트로미노가 가질수 있는 최대값을 물어보는 문제였습니다. 도형들의 길이가 4이기 때문에 각 좌표마다 DFS탐색을 통해 4번째 탐색이 되었을때의 합계의 값을 최대가 되게 비교해주면 되는 방법으로 해결하였습니다. 이 방법으로 문제를 해결하면 예외가 한 가지 존재하는데 'ㅗ' 도형일 경우 DFS 탐색을 통해 모든 경우를 탐색하는게 불가능합니다. 왜냐하면 튀어나온 부분으로 들어갔다가 다시 돌아와서 탐색이 DFS로는 불가능하기 때문입니다. 이 부분만 저는 따로 함수를 구현해서 예외처리 해주..
14499-주사위굴리기
문제 https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도 www.acmicpc.net 접근방법 1) 접근 사고 주사위를 돌리는 구현을 구현해주는게 핵심이었습니다. 주사위가 이동방향으로 움직였을때 표현을 이동방향에 맞게 내부값들을 이동시켜주었습니다. 2) 시간 복잡도 n의 범위가 크지 않아 N^2으로도 탐색이 가능합니다. 3) 배운 점 기능마다 나눠서 객체지향적(?)으로 구현해보았습니다. 4) PS 정답 코드 1..
13458번-시험감독
문제 https://www.acmicpc.net/problem/13458 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net 접근방법 1) 접근 사고 간단한 구현 문제였습니다. 생길 수 있는 경우의수를 구분해서 결과값에 반환해주면 되는 문제입니다. 다만 한 가지 주의해야 할 점이 있습니다. 2) 시간 복잡도 n의 범위가 1부터 1,000,000 A의 범위가 1,000,000 이므로 최악의 경우 한 강의실에 응시생이 1,000,000 이라면 1,000,000,..
3190번-뱀
문제 https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 접근방법 1) 접근 사고 문제의 조건을 보면 단순 구현 문제란걸 알 수 있었다. 2) 시간 복잡도 n의 범위가 작아서 완전탐색이 가능하다 3) 배운 점 구현에 초점이 맞춰져 있는 문제이다. 61번줄 부터의 인덱스 계산을 효율적으로 계산하는 코드를 배웠다. 자세한 풀이는 코드 참조 4) PS 삼성문제를 갈아먹고 씹어먹어 주겠다. 정답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1..
11657번-타임머신
문제 https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. 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 46 47 48 49 50 5..
3830번-교수님은 기다리지 않는다.
문제 https://www.acmicpc.net/problem/3830 3830번: 교수님은 기다리지 않는다 교수님의 질문 (? a b)이 입력으로 들어올 때 마다, 지금까지 측정한 결과를 바탕으로 a와 b의 무게 차이를 계산할 수 있다면, b가 a보다 얼마나 무거운지를 출력한다. 무게의 차이의 절댓값이 1,000, 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 46 47 48 49 50 51 52 53 54 55 56 5..
1516번-게임개발
문제 https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 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 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60..
2458번-키순서
문제 https://www.acmicpc.net/problem/2458 접근방법 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 46 47 48 49 50 51 #include #define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) #define pii pair #define mp(X,Y) make_pair(X,Y) #define mt(X,Y) make_tuple(X,Y) #define mtt(X,Y,Z..
2252번-줄 세우기
문제 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 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 46 47 48 49 50 51 52 53 #i..
5719번-거의 최단 경로
문제 https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 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 46 47 48 49 50 51 52 53 54 55 56 ..
2211번-네트워크 복구
문제 https://www.acmicpc.net/problem/2211 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다 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 46 47 48 49 50 51 52 53 54 55 56 57..
1922번-네트워크 연결
문제 https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. 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 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 #include #d..
1916번-최소 비용 구하기
문제 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 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 46 47 48 49 50 51 52 53 54 55 5..
1854번-K번째 최단경로 찾기
문제 https://www.acmicpc.net/problem/1854 1854번: K번째 최단경로 찾기 첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이어지는 m개의 줄에 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 46 47 48 49 50 51 ..
1753번-최단경로
문제 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 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 46 47 48 49 50 51 52 53 54 55 56 57..
16681번-등산
문제 https://www.acmicpc.net/problem/16681 16681번: 등산 첫 번째 줄에 지도에 표시된 지점의 개수, 지점을 잇는 경로의 개수, 주환이의 거리 비례 체력 소모량, 높이 비례 성취감 획득량을 나타내는 정수 N, M, D, E가 공백을 사이에 두고 주어진다. (2 ≤ 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 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 ..
1504번-특정한 최단 경로
문제 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 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 46 47 48 49 50 51 52 53 5..
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 ..
11727번-2*n 타일링2
문제 https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 접근방법 1) 접근 사고 11726번과 유사하다 가로만 봐주기 때문에 n - 2인 경우를 하나 더 더 해주면 된다. 왜냐하면 2*2 타일의 가로는 2이기 때문이다. 2) 시간 복잡도 O(n) 3) 배운 점 11726번 응용 정도인거 같다. 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 3..
11726번-2*n 타일링
문제 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 접근방법 1) 접근 사고 가로만 봐주면 되는 문제이다. 왜냐하면 가로를 2간 채워서 넣을 것인지 1칸 채워서 넣을 것인지만 봐주면 되기 때문이다. 2) 시간 복잡도 O(n)으로 해결 간으! 3) 배운 점 배열에서 인덱스를 계산해주는 문제와 유사한거 같다. 규칙을 찾아서 점화식을 만들어 푸는 방법도 존재한다. 4) PS 정답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19..
1932번-정수 삼각형
문제 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 접근방법 1) 접근 사고 배열이 주어지고 재귀함수를 y,x의 인덱스 값을 가지고 이동시키면서 비교연산을 통해 큰 값을 반환해주면 되는 문제였습니다. 저는 탑다운 형식으로 구현하였습니다. 2) 시간 복잡도 O(n)에 해결되는 문제였습니다. 3) 배운 점 배열에서 인덱스를 통한 이동값을 구하는 문제가 간혹 출제되는거 같은데 일종의 틀이 정해져 있는거 같아서 유형을 복습하기에 좋았습니다. 4) PS 비슷한 유형의 문제를 풀다가 const int max를 통한 배열값 지..
1890번-점프
문제 https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 접근방법 1) 접근 사고 문제에서 "반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다." 라는 힌트로 두 가지의 경우로 나뉘며 재귀함수로 코드를 작성하면 구현이 쉬울 거 같은 설명이 적혀있다. 2) 시간 복잡도 다이나믹 프로그래밍을 활용하여 접근하였으므로 O(n)의 시간복잡도를 가진다...
1912번-연속합
문제 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 접근방법 1) 접근 사고 처음에는 이분탐색으로 구현을 할 려고 했었다. 그러나 이분탐색 부분을 구현하던 도중 두 개의 값을 더 한것을 어떻게 표현할 것인지에 대해 막혀서 다시 고민을 했었고 두 개를 더할 것인가 말 것인가에서 DP로 점화식을 세우면 될 것 같다고 생각을 하였다. 2) 시간 복잡도 DP로 구현을 하였으므로 시간초과 관련 문제는 없었다. 자료형도 최대 100,000 * 1000 = 1,00..
1463번-1로 만들기
문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 접근방법 1) 접근 사고 X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 이런 형식으로 문제에서 재귀함수로 구현하면 구현하기 쉽게 힌트를 준다. 이런 방식을 완전탐색으로 풀려고 접근하여 각각의 경우에서 수 많개의 경우의 수로 분할 되기 때문에 시간초과가 나므로 시간복잡도를 줄여야 하는 문제임을 알 수 있다. 2) 시간 복잡도 memorization 기법을 사용한 DP로 접근 3) 배운 점 memorization을 활용해서 탑다운 방식의 알고리즘을 구현해..
9461번-파도반수열
문제 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 접근방법 1) 접근 사고 문제에서 보면 누가봐도 규칙을 찾으라고 예시까지 친절하게 준다. 2) 시간 복잡도 완전탐색으로는 구현할 방법이 떠오르지 않는 문제. 삼각형의 예시를 보면서 점화식을 찾아야 하는 문제이다. 3) 배운 점 문제에서 n은 100까지 인데 문제를 보면서 규칙을 찾다보면 점화식이 cache[n] = cache[n - 2] + cache[ n - 3]인걸 알 수 있다. 그러므로 숫자..