https://www.acmicpc.net/problem/14714 14714번: 홍삼 게임 (Easy) 첫 번째 줄에 “질서 있는 홍삼 게임”의 참가자의 수 N(2 ≤ N ≤ 500), 은하가 먼저 지목한 사람의 번호 A와 두 번째로 지목한 사람의 번호 B(1 ≤ A, B ≤ N, A ≠ B), 각 지목권의 지목 간격을 나타내 www.acmicpc.net 문제 유형을 보면 힌트를 얻을 수 있는데, BFS를 사용하여 풀 수 있는 문제였다.. 방문 처리를 할 때 지목권 a를 가질 사람을 탐색 & 지목권 b를 가질 사람을 탐색 해야 하며 각 turn 마다 지목은 한번만 하므로 이를 3차원 배열로 나타낼 수 있다는 것이 이 문제의 핵심이었다 즉 이를 3차원 배열로 표현하게 되면 visited[지목권 종류][a..
백준
예전에 풀었었는데, 재채점 이후에 틀렸다고 그래서 다시 풀게 되었다. https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, www.acmicpc.net 1차 시도 # https://www.acmicpc.net/problem/17142 import sys from collections import deque from itertools import combinations input = sys.stdin.readline dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] n..
https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 오 어제 풀었던 백준 5547 일루미네이션 문제와 상당히 유사한 접근법으로 풀이하면 되는 BFS/DFS문제였다. [ 문제 풀이 아이디어 ] i) 0과 인접한 1 찾기 공기 칸(값이 0인 칸)을 중심으로 bfs 탐색을 하고, 공기 칸이 치즈 칸 (값이 1 인 칸)을 만나게 되면 치즈칸에 += 1을 해준다. 탐색이 종료되었을 때 array[i][j] 의 값이 3이상이면 맞닿는 공기 칸이 ..
https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net dp 는 3 * (n+1)의 공간으로 만들어 주었다. 사자를 배치하는 것에 대해 생각해보면 다음과 같은 세 가지 이다. 1. 사자를 배치하지 않는 경우 dp[i][0] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2] 2. 사자를 왼쪽 칸에 배치하는 경우 사자를 연속해서 왼쪽 칸에 배치할 수 없으므로, 이전 계산 값 (dp[i-1])에서 오른쪽에 배치한 경우와 배치하지 않는 경우의 수를 가져온다. dp[i][1] = dp[i-1][0] + dp[i-1][2] 3. 사자를 오른 쪽 칸에 배치하는 경우 사자를 연속..
https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net DFS로 풀이했다. 나 근데 가로 세로가 아직 헷갈린다;; 아이디어는 다음과 같다. n = 7, m = 5 사이즈의 2차원 배열 (= 그래프) 가 있다고 생각하면, 각 칸을 모두 0으로 초기화 시킨다 입력되는 직사각형 부분에 해당하는 칸들은 2차원 배열에서 1로 표시한다. 1은 이미 방문된 노드라는 의미이다. 그후 전체 2차원 배열을 이중 for문으로 하나씩 칸의 값을 체크하면..
https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 쉽지않은 계단수 문제였따 .. 여기서 (0-9)는 맨 끝자리수이고 N은 문제에서와 같이 자리수를 뜻한다. 규칙은 이렇게 각 끝자리수의 개수를 대각선 방향 왼쪽 위 + 대각선 방향 오른쪽 위 를 더하면 구할 수 있다. 즉, dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] 라는 식이 나온다 !!! 끝자리 수가 0, 9일때는 각각 한쪽방향의 대각선에서만 존재하니까 그 수를 그대로 옮겨오면 된다. 위의 그림에서는 파란 선을 참고! 자리수가 1일때 (한자리수)일 때는 직접 초기화를 해주어야 한다. ..
https://www.acmicpc.net/status?user_id=freemjstudio&problem_id=15666&from_mine=1 채점 현황 www.acmicpc.net 두번째 예시로 생각해보자 i) 중복 제거 n = 4, m = 2 그리고 후보로 주어진 숫자들은 9 7 9 1 이다. 어처피 우리는 중복해서 같은 숫자를 선택할 수 있으므로 중복을 set() 함수를 통해 제거한 후 다시 list로 형변환한다. 그러면 9 7 1 세가지가 남는다. 비내림차순이라는 조건이 주어졌으므로 -> 오름차순으로 바꿔봅시다. 그러면 후보들을 정렬했을 때 1 7 9 가 됩니다. ii ) for문과 재귀함수 호출 우리는 이제 1 7 9 세가지 선택지가 있고 이 세가지 숫자들을 for문을 통해서 순회하며 하나씩 ..
https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 이 문제를 풀 때 핵심적인 아이디어는, 뒤쪽 날짜부터 거꾸로 확인하는 방식으로 다이나믹 프로그래밍 알고리즘을 수행해야 한다는 것이다 ! 문제에서 주어진 예시 N = 7 인 경우에는 6일과 7일자의 상담을 수행하면 7을 넘기게 된다. 이와 같은 경우를 고려하기 위해서 뒤에서부터 DP를 수행하여 저장한다. 경우를 나누는 것은 두가지로, i번째 날의 상담을 수행했을 때 n을 넘는다면 이 경우는 불가능하니까 value를 0이라고 생각하여 dp 그래프에 0 값으로 처리를 한다. dp[i] = dp[i+1] # 단, 여기서 dp list의 맨 ..
