devlog

출처 : 17070번: 파이프 옮기기 1 (acmicpc.net) 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 풀이 방법 bfs로 파이프의 머리 부분의 좌표와 가로로, 대각선, 세로 상태를 queue에 넣어 주었다. 각 상태에 따라 can_right, can_diagonal, can_bottom를 사용하여 이동할 수 있는지 판별 후 이동할 수 있으면 queue에 넣어주었다. 그리고 파이프의 머리가 도착지점에 도달하면 cnt++을 해주어 답을 찾았다. // 1600 #include u..

출처 : 7569번: 토마토 (acmicpc.net) 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 풀이 방법 다른 문제들과 달리 3차원 상황이다. 2차원과 비슷한 방법으로 방향 배열을 만들어 주면 된다. int dy[6] = {0, 0, -1, 1, 0 ,0}; int dx[6] = {0, 0, 0, 0, -1, 1}; int dz[6] = {1, -1, 0, 0, 0, 0}; 입력을 받으면서 익은 토마토가 나오면 q에 좌표를 추가해 주고 입력을 받은 후 bfs를 실행하면 된다 실행..

출처 : 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..