devlog

출처 : 10844번: 쉬운 계단 수 (acmicpc.net) 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 방법 계단 수는 +1 또는 -1 차이가 난다. dp[i][j]를 i자리 수 이면서 j로 시작하는 수로 잡는다 그러면 dp[i][j] = dp[i-1][j+1] + dp[i-1][j-1] 이 된다 주의할 점은 j가 0이면 1로 시작하는 수만 와야하고 j가 9면 8로 시작 한느 수만 올 수 있어 예외 처리를 해주면 된다. //11057 #include using namespace std ; int n; vector num; long long dp[101][10]; long long ans = 0; void solv..

출처 : 2156번: 포도주 시식 (acmicpc.net) 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 풀이 방법 현재 인덱스 포도주를 기준으로 몇 번 연속인지 계산하면 문제를 쉽게 풀이할 수 있다. 0번째 연속인 경우 dp[i] = dp[i-1] // i번째 포도주를 마시지 않는 경우 1번째 연속인 경우 dp[i] = dp[i-2] + wine[i] // i-2 번째 dp에서 i-1번째 포도주를 건너뛰고 i번째 포도주를 마신 경우 2번째 연속인 경우 dp[i] = dp[i-3] + wine[i-1] + w..

출처 : 2638번: 치즈 (acmicpc.net) 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 풀이 방법 dfs로 풀이하였다 모눈종이의 가장자리가 비어있다고 가정했으므로 치즈 밖의 공기들은 다 연결되어있다. 치즈 밖의 공기는 다 연결되어있으므로 dfs(0,0)으로 하면 다 탐색할 수 있다. 탐색 중 보드 값이 1인 치즈를 만나면 +1을 해주어 보드 값을 2로 만들어 주고 탐색중 보드 값이 2인 치즈를 만나면 mel_cheese벡터에 추가해 주고 visited 값을 1로 바꾸어 주어 다시 방문..

출처 : 1520번: 내리막 길 (acmicpc.net) 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 풀이 방법 처음에는 dfs로 풀이하였는데 시간 초과가 나서 dfs에 dp를 적용해서 풀이하여 통과하였다. #include using namespace std ; int M, N, ans = 0; int dp[501][501]; vector board; int dx[4] = {1, -1, 0, 0}; int dy[4] = {0, 0, 1, -1}; int dfs(int y,int x) { if (y == M-1 ..

출처 :7562번: 나이트의 이동 (acmicpc.net) 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 풀이 방법 문제에서 몇 번 만에 갈 수 있는지 구하라 했으므로 bfs를 사용하여 풀이하였다 다른 보편적인 문제(상하 좌우 이동)와 다른 점은 나이트의 이동 경로가 8가지로 다르게 정해져 있었다. 이동 경로를 dy, dx에 저장해 두고 이용하였다. #include using namespace std ; int visited[301][301]; int dy[8] = {1, 2, 2, 1, -1, -2, -2,..

출처 : 9251번: LCS (acmicpc.net) 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 방법 비슷한 문제를 풀어봐서 쉽게 접근 할 수 있었다. 2차원 배열을 만든 뒤 i인덱스는 문자열 0부터 i까지의 문자열1과 0부터 j까지 문자열2 까지의 LCS를 구한 것이다. 배열에서 만약 i인덱스 문자와 j문자의 인덱스가 같으면 i-1, j-1인덱스 의 값에 +1 한 것이고. 만약 다르다면 i-1, j or i, j-1 의 값중 큰 값을 넣으면 된다. #i..

출처 : 1987번: 알파벳 (acmicpc.net) 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 풀이 방법 bfs로 풀지 dfs로 풀지 고민하다 지금 까지 지나온 알파벳을 저장하고 알파벳 방문 여부를 판단하기에 dfs가 더 적합할 거 같아서 dfs 로 풀이하였다. 알파벳은 26개의 배열을 만들어 방문했으면 배열에 1로 두고 두 번 방문하지 않게 하였다. 그리고 백트레킹을 활용하여 더 이상 갈 곳이 없으면 배열을 다시 초기화하여서 다른 방향에서 방문을 할 수 있도록 하였다. #include usin..

출처 : 5014번: 스타트링크 (acmicpc.net) 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 풀이 방법 경우가 올라가고 내려가는 2경우 밖에 없으므로 bfs를 통해 탐색했다. bfs의 큐를 통해 방문하지 않은 층이라면 내려가는 경우와 올라가는 경우 두 개의 층을 범위가 벗어 나지 않으면 큐에 추가해주었다. 그리고 visited를 활용해 몇번 움직였는지를 저장해 주었다. #include using namespace std; // boj num 5014 int F, S, G, U, D; int visited[10..

출처 : 1946번: 신입 사원 (acmicpc.net) 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 풀이 방법 서류심사와 면접시험이 둘 다 어떤 사람보다 낮으면 채용되지 않는다고 문제에 설명되어 있다. 서류심사 등수 기준으로 정렬을 한 뒤 서류심사 1등은 무조건 채용된다. 서류심사 1등의 면접 등수를 temp라는 변수에 저장한뒤 for문을 돌며 temp보다 좋은 등수를 받은 사람이 있으면 이 사람의 면접 등수를 temp에 저장해주고 ans를 +1해준다 이 과정을 for문 끝까지 반복..

출처 : 2589번: 보물섬 (acmicpc.net) 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 풀이 방법 그래프 문제인데 시작점을 여러번 바꿔가면서 bfs를 수행하여야 한다. 그래서 완전 탐색(Brute Force)를 이용하여 육지에서의 거리가 가장 먼 값을 구하여 답으로 출력 해야한다. 여기서 visited에 거리를 저장하는데 시작점을 1로 두어야 다시 시작점을 방문하는 오류를 줄일수 있어 시작점의 visited 값을 1로 설정한뒤 마지막에 답을 출력할때 -1을 해준다. #include using nam..