1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net BFS + DFS 제목 이분 그래프 조건 시간 제한 : 2 초 메모리 제한 : 256 MB 문제 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. 그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오. 입력 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이..
17213번: 과일 서리 민건이네 과일 농장은 N가지 종류의 과일을 재배하는 중이다. 평소 민건이에게 앙심을 품고 있던 지환이는 민건이를 골탕 먹이기 위하여 민건이네 과일 농장에서 과일들을 훔치기로 다짐했다. www.acmicpc.net 파스칼의 삼각형 + DP 제목 과일 서리 조건 시간 제한 : 1 초 메모리 제한 : 256 MB 문제 민건이네 과일 농장은 N가지 종류의 과일을 재배하는 중이다. 평소 민건이에게 앙심을 품고 있던 지환이는 민건이를 골탕 먹이기 위하여 민건이네 과일 농장에서 과일들을 훔치기로 다짐했다. 지환이는 완벽한 범죄를 위하여 처음 생각한 개수 만큼만 훔치려고 한다. 이때 지환이가 훔칠 수 있는 경우의 수가 몇가지나 될 지 알아보자. 단, 모든 종류의 과일을 적어도 1개는 훔친다. ..
20149번: 선분 교차 3 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net CCW + 기울기가 무한일 때와 유한일 때 제목 선분 교차 3 조건 시간 제한 : 0.25 초 메모리 제한 : 512 MB 문제 2차원 좌표 평면 위의 두 선분 L1, L2가 주어졌을 때, 두 선분이 교차하는지 아닌지 구해보자. 한 선분의 끝 점이 다른 선분이나 끝 점 위에 있는 것도 교차하는 것이다. L1의 양 끝 점은 (x1, y1), (x2, y2), L2의 양 끝 점은 (x3, y3), (x4, y4)이다. 입력 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x..
17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net CCW 제목 선분 교차 2 조건 시간 제한 : 0.25 초 메모리 제한 : 512 MB 문제 2차원 좌표 평면 위의 두 선분 L1, L2가 주어졌을 때, 두 선분이 교차하는지 아닌지 구해보자. 한 선분의 끝 점이 다른 선분이나 끝 점 위에 있는 것도 교차하는 것이다. L1의 양 끝 점은 (x1, y1), (x2, y2), L2의 양 끝 점은 (x3, y3), (x4, y4)이다. 입력 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. 출력 L1과 ..
17386번: 선분 교차 1 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. 세 점이 일직선 위에 있는 경우는 없다. www.acmicpc.net CCW 제목 선분 교차 1 조건 시간 제한 : 0.25 초 메모리 제한 : 512 MB 문제 2차원 좌표 평면 위의 두 선분 L1, L2가 주어졌을 때, 두 선분이 교차하는지 아닌지 구해보자. L1의 양 끝 점은 (x1, y1), (x2, y2), L2의 양 끝 점은 (x3, y3), (x4, y4)이다. 입력 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. 세 점이 일직선 위에 있는 경우는 없다. 출력 ..
1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 제목 리모컨 조건 시간 제한 : 2 초 메모리 제한 : 256 MB 문제 수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다. 리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다. 수빈이가 지금 ..
9999번: 구구 구구 구구구 구구구 구구구구구구 구구구구 구구구구 구구구 구구구 구구구 구구구 구구구구구 구구구구 구구구 구구구구구구 구구 구구구 구구구 구구구구구 구구구구 구구 구구구구 구구구 www.acmicpc.net 백준 페이스북 페이지에 적힌 첫번째 힌트 문제의 힌트에 써있는 노래는 1915년에 태어난 사람이 1950년에 발매한 앨범에 수록된 노래입니다. + 백준 페이스북 페이지에 적힌 두번째 힌트 EP 제목 구구 조건 시간 제한 : 1 초 메모리 제한 : 128 MB 문제 구구 구구구 구구구 구구구구구구 구구구구 구구구구 구구구 구구구 구구구 구구구 구구구구구 구구구구 구구구 구구구구구구 구구 구구구 구구구 구구구구구 구구구구 구구 구구구구 구구구구구 구구구구 구 구구구구 구구구구 구 구구구..
15891번: 스타트링크 사무실을 파헤쳐보자 UCPC 2018 운영진은 지금 스타트링크 사무실에 와서 벼락치기로 대회를 준비하고 있다. 예비소집용 문제로 무엇을 출제할지 고민하던 ntopia는 사무실을 둘러보다가 아주 적절한 문제를 생각해냈 www.acmicpc.net 틀리면서 풀어야하는 문제 제목 스타트링크 사무실을 파헤쳐보자 조건 시간 제한 : 1 초 메모리 제한 : 512 MB 문제 UCPC 2018 운영진은 지금 스타트링크 사무실에 와서 벼락치기로 대회를 준비하고 있다. 예비소집용 문제로 무엇을 출제할지 고민하던 ntopia는 사무실을 둘러보다가 아주 적절한 문제를 생각해냈다. 스타트링크 사무실을 소재로 퀴즈를 내는 것이다! 퀴즈는 아래와 같다. 아래 퀴즈에서 X에 들어가는 자연수가 퀴즈의 답이 ..
2556번: 별 찍기 - 14 지금까지 안 나온 별 찍기가 뭐가 있는지 생각해본 후, 별을 적절히 찍으세요. www.acmicpc.net 출제자가 사과한 문제 정사각형 제목 별 찍기 - 14 조건 시간 제한 : 1 초 메모리 제한 : 128 MB 문제 지금까지 안 나온 별 찍기가 뭐가 있는지 생각해본 후, 별을 적절히 찍으세요. 입력 첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다. 출력 N개의 줄에 걸쳐 별을 적절히 찍는다. 예제 입력1 예제 출력1 1 * #include #include using namespace std; int main() { int num; cin >> num; for (int n = 0; n < num; n++) { for (int m = 0; m < num; m++) { cout
2555번: 생일 출력하기 월/일 형식으로 출력하면 된다. 예를 들어, 7월 4일인 경우에는 7/4, 9월 20일인 경우에는 9/20, 11월 4일인 경우에는 11/4와 같이 출력하면 된다. www.acmicpc.net About BOJ Baekjoon Online Judge 소개 Baekjoon Online Judge는 2010년 3월 19일부터 운영을 시작한 온라인 저지 입니다. 온라인 저지는 주로 ICPC 대회를 준비할 때 사용합니다. 프로그래밍 문제를 해결한 다음, 소스를 제출하고 온라인으로 www.acmicpc.net 제목 생일 출력하기 조건 시간 제한 : 1 초 메모리 제한 : 128 MB 문제 이 문제가 있는 사이트의 생일을 출력하시오. 입력 월/일 형식으로 출력하면 된다. 예를 들어, 7월..
1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 제목 최소비용 구하기 조건 시간 제한 : 0.5 초 메모리 제한 : 128 MB 문제 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다. 입력 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주..
2162번: 선분 그룹 첫째 줄에 N(1 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N+1번째 줄에는 양 끝점의 좌표가 x1, y1, x2, y2의 순서로 주어진다. 각 좌표의 절댓값은 5,000을 넘지 않으며, 입력되는 좌표 사이에는 빈칸이 하 www.acmicpc.net CCW + Union Find ALG 제목 선분 그룹 조건 시간 제한 : 2 초 메모리 제한 : 128 MB 문제 N개의 선분들이 2차원 평면상에 주어져 있다. 선분은 양 끝점의 x, y 좌표로 표현이 된다. 두 선분이 서로 만나는 경우에, 두 선분은 같은 그룹에 속한다고 정의하며, 그룹의 크기는 그 그룹에 속한 선분의 개수로 정의한다. 두 선분이 만난다는 것은 선분의 끝점을 스치듯이 만나는 경우도 포함하는 것으로 한다. N개의..
