넘치게 채우기

https://www.acmicpc.net/problem/13460BOJ - 구슬 탈출 2문제 유형: bfs, 시뮬레이션, 그래프문제 난이도: Gold I시간 제한: 2초메모리 제한: 512MB 문제스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다.보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다. 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이즈이고, 각각 하나씩 들어가 있다. 게임의 목표는 빨간 구슬을 구멍을 통해서 ..

https://www.acmicpc.net/problem/1707BOJ - 이분 그래프문제 유형: 그래프, bfs/dfs, 이분 그래프문제 난이도: Gold IV시간 제한: 2초메모리 제한: 256MB 문제그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오. 입력입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 두고 순서대로 주어진다..

https://www.acmicpc.net/problem/11403BOJ - 경로 찾기문제 유형: 플로이드-워셜, 그래프, 최단 거리문제 난이도: Silver I시간 제한: 1초메모리 제한: 256MB 문제가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오. 입력첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다. 출력총 N개의 줄에 걸쳐서 문제의 정답을 인접행렬 형식으로 출력..

https://www.acmicpc.net/problem/1562BOJ - 계단 수문제 유형: 다이나믹 프로그래밍, 비트마스킹문제 난이도: Gold I시간 제한: 2초메모리 제한: 128MB 문제45656이란 수를 보자.이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.N이 주어질 때, 길이가 N이면서 0부터 9까지 숫자가 모두 등장하는 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. 0으로 시작하는 수는 계단수가 아니다. 입력첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 출력첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. 풀이0~9이므로, 등장여부 상태를 비트마스킹을 이용할 수 있다. (처음에 상태추적을..

https://www.acmicpc.net/problem/9328BOJ - 열쇠문제 유형: 구현, bfs, 그래프, 시뮬레이션문제 난이도: Gold I시간 제한: 1초메모리 제한: 256MB 문제상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 필요하다. 상근이는 일부 열쇠를 이미 가지고 있고, 일부 열쇠는 빌딩의 바닥에 놓여져 있다. 상근이는 상하좌우로만 이동할 수 있다.상근이가 훔칠 수 있는 문서의 최대 개수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다.각 테스트 케이스의 첫째 줄에는 ..

https://www.acmicpc.net/problem/17387BOJ - 선분 교차 2문제 유형: 선형대수, 수학, 기하학문제 난이도: Gold II시간 제한: 0.25초메모리 제한: 512MB 문제2차원 좌표 평면 위의 두 선분 L1, L2가 주어졌을 때, 두 선분이 교차하는지 아닌지 구해보자. 한 선분의 끝 점이 다른 선분이나 끝 점 위에 있는 것도 교차하는 것이다.L1의 양 끝 점은 (x1, y1), (x2, y2), L2의 양 끝 점은 (x3, y3), (x4, y4)이다. 입력첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. 출력L1과 L2가 교차하면 1, 아니면 0을 출력한다. 풀이처음에는 직선의 방정식을 이용해서..

https://www.acmicpc.net/problem/2568BOJ - 전깃줄 - 2문제 유형: 가장 긴 증가하는 부분 수열(LIS), 다이나믹 프로그래밍문제 난이도: Platinum V시간 제한: 1초메모리 제한?: 128초 문제두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다.예를 들어, 과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다.   전깃줄이 전봇대에 연결..

https://www.acmicpc.net/problem/10775BOJ - 공항문제 유형: 분리 집합, 그리디문제 난이도: Gold II시간 제한: 1초메모리 제한: 256MB 문제오늘은 신승원의 생일이다.박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다.공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다.공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다.신승원은 가장 많은 비행기를 공항에 도킹시켜서 박승원을 행복하게 하고 싶어한다. 승원이는 비행기를 최대 몇 대 도..

https://www.acmicpc.net/problem/28707BOJ - 배열 정렬문제 유형: 문자열 처리, 최단 경로, 다익스트라, 해시문제 난이도: Gold I시간 제한: 1초메모리 제한: 1024MB 문제길이가 N인 양의 정수로 이루어진 배열 A=[A1,A2,⋯,AN]이 주어집니다. 이 배열을 비내림차순, 즉, A1≤A2≤⋯≤AN이 되도록 정렬하기 위해서 다음과 같은 M가지 조작을 순서와 횟수에 상관 없이 원하는 만큼 할 수 있습니다. A의 li번째 수와 ri번째 수를 바꿉니다. 비용은 ci가 듭니다. (1≤i≤M) A를 비내림차순으로 정렬하기 위해 필요한 비용 총합의 최솟값을 출력하세요. 입력첫 줄에 배열 A의 길이 N이 주어집니다. (2≤N≤8)둘째 줄에 A의 각 원소 A1,⋯,AN이 공백으..

https://www.acmicpc.net/problem/1799BOJ - 비숍문제 유형: 백트래킹, 브루트 포스, MITM(Meet-In-The-Middle)문제 난이도: Platinum V시간 제한: 10초메모리 제한: 128MB 문제서양 장기인 체스에는 대각선 방향으로 움직일 수 있는 비숍(bishop)이 있다. 과 같은 정사각형 체스판 위에 B라고 표시된 곳에 비숍이 있을 때 비숍은 대각선 방향으로 움직여 O로 표시된 칸에 있는 다른 말을 잡을 수 있다.그런데 체스판 위에는 비숍이 놓일 수 없는 곳이 있다. 에서 체스판에 색칠된 부분은 비숍이 놓일 수 없다고 하자. 이와 같은 체스판에 서로가 서로를 잡을 수 없도록 하면서 비숍을 놓는다면 과 같이 최대 7개의 비숍을 놓을 수 있다. 색칠된 부분에는..