중점 1. 시간 제한이 0.25초라는 것 2. 피보나치 수열을 사용하면서 0과 1이 출력되는 수를 구하는 것 설명: 재귀 함수를 이용하여서 피보나치 풀이를 하기에는 시간 제한이 있으므로 출제자가 원하는 풀이가 아니라고 할 수 있다. 따라서 DP알고리즘을 이용해서 풀이 해야한다는 생각을 할 수 있다. 이를 생각하게된 계기는 문제에서 피보나치 수열을 사용할 때 0과 1이 출력되는 수 count하는 것에서 아이디어를 얻었다. 이는 즉 초기값인 f(0)과 f(1)로 f(n)을 만드는 것과 같다. 예를 들면 f(2) = f(0) + f(1)이고 f(3) = f(2) + f(1)이다. 이를 다르게 표현하면 f(3) = 2f(1) + f(0)이라는 뜻이다. 따라서 각각의 n에 대해서 얼마의 0과 1로 이루어져 있는지..
coding-test
중점 1. 같은 구조인지를 파악하는 것 - vis에 숫자로 저장함 2. bfs를 두번 사용, vis, board를 2개씩 정의 3. 첫번째 bfs에서 vis의 구조를 확인하며 두번째 bfs를 돌린다. 정답 코드 #include using namespace std; #define X first #define Y second int n, m; string board1[52]; string board2[52]; int vis1[52][52]; int vis2[52][52]; int dx[] = {1, 0, -1, 0}; int dy[] = {0, 1, 0, -1}; int main(void){ ios::sync_with_stdio(0); cin.tie(0); int count = 1; cin >> n >> m..
중점: 1. 기본 bfs알고리즘의 활용 2. 범위를 벗어나는 경우 continue를 했지만 이번 경우에는 nx, ny의 값을 최신화함. 정답 코드: #include using namespace std; #define X first #define Y second int n, m; int board[1002][1002]; int vis[1002][1002]; int dx[] = {1, 0, -1, 0}; int dy[] = {0, 1, 0, -1}; int main(void){ ios::sync_with_stdio(0); cin.tie(0); int count = 0; cin >> n >> m; for (int i = 0; i ..
정점: 1. 1차원 배열 사용 2. bfs알고리즘 안 dir에서 +1, *2에 대해서 vis 값 최신화한다. 정답 코드: #include using namespace std; int a, k; int vis[1000001]; int main(void){ ios::sync_with_stdio(0); cin.tie(0); cin >> a >> k; queue Q; Q.push(a); while (!Q.empty()) { int cur = Q.front(); Q.pop(); if (cur == k){ break; } if (cur + 1
중점: 1. 열에 3을 곱하여서 행렬을 만든다. 2. 각 행렬에 대해서 +3씩 추가되는 for문을 만들어서 평균을 구하고 t값에 따라서 board값을 바꿈 3. 시작점을 찾는 로직, 개수를 찾는 로직 사용 정답 코드: #include using namespace std; #define X first #define Y second int n, m, t; int board[3002][3002]; int vis[3002][3002]; int dx[] = {1, 0, -1, 0}; int dy[] = {0, 1, 0, -1}; int main(void){ ios::sync_with_stdio(0); cin.tie(0); int count = 0; cin >> n >> m; m = 3 * m; for (int i..
중점: 1. bfs 알고리즘을 사용 2. 적록색약인 경우 board의 값을 변경 3. 각 bfs에 대해서 count를 달리하여서 출력 정답 코드: #include using namespace std; #define X first #define Y second string board[102]; int vis[102][102]; int n; int dx[] = {1, 0, -1, 0}; int dy[] = {0, 1, 0, -1}; int main(void){ ios::sync_with_stdio(0); cin.tie(0); int nomal_count = 0; int color_count = 0; cin >> n; for (int i = 0; i > board[i]; } qu..
