💡 Problem Solving

[백준 - 1436] 영화감독 숌 [C++]

1. 문제 https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net 2. 풀이과정 종말의 숫자란 어떤 수에 6이 적어도 3개이상 연속으로 들어가는 수이다. N번째로 작은 종말의 숫자를 찾는 문제이다. 1, 2, 3, 4, .... 모든 수를 검사하며 해당 수가 종말의 수이면 개수를 세서 개수가 N이 되면 해당 숫자를 출력해주면 된다. [코드설명] num 변수는 숫자를 하나씩늘리는 변수이다. 6이 적어도 3개 들어가면 되므로 숫자를 문자열로 바꿔서 "6..

[백준 - 15663] N과 M (9) [C++]

1. 문제 https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 2. 풀이과정 N개의 자연수 중에서 M개를 고른 수열을 출력하는 문제인데, 아래의 조건들을 만족해야한다. 1. 중복되는 수열을 여러 번 출력하면 안된다. 2. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. N = 4, M = 2 N개의 수 = {9, 7, 9, 1}일 때, 1 7 1 9 7 1 7 9 9 1 9 7 9 9 가 출력되어야 한다. 2번 조건을 만족하기 위해 N개의 수..

[백준 - 2529] 부등호 [C++]

1. 문제 https://www.acmicpc.net/problem/2529 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제 www.acmicpc.net 2. 풀이과정 1. 부등호의 개수인 k보다 하나 많은 k+1개의 수를 나열한다. 2. 나열된 수들이 주어진 부등호 관계들을 만족하는지 판별한다. 3. 만족하면 결과 벡터에 저장한다. [코드설명] dfs함수는 k+1개의 수들을 나열한다. k=2이라면, 0 1 2 0 1 3 0 1 4 . . 7 8 9 와 같은 순서로 수를 나열한다. check함수는 나열된 수들이 입력받은 부등호관계를 만족하는 지 여부를..

[백준 - 2108] 통계학 [C++]

1. 문제 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 2. 풀이과정 N개의 수에 대해 산술평균 : N개의 수들의 합을 N으로 나눈 값 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값 최빈값 : N개의 수들 중 가장 많이 나타나는 값 범위 : N개의 수들 중 최댓값과 최솟값의 차이 를 구해주면 된다. [코드설명] 먼저 중앙값, 범위 등을 쉽게 구하기 위해 n개의 수를 입력받은 후 sort로 오름차순 정렬해준다. average함수는 산술평균을 반환해준다. n개의 수를 더해서 n으로 나눈 후 소수점 이하 첫째 자리..

[백준 - 14502] 연구소 [C++]

1. 문제 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 2. 풀이과정 1. 연구소의 빈 칸 3곳에 벽을 세운다. 2. 바이러스를 퍼뜨린다. 3. 안전영역의 크기를 구하고 최댓값을 갱신한다. 이때 벽을 세울 수 있는 모든 경우의 수에 대해 1~3을 반복한다. [코드설명] main함수의 3중 for문으로 벽을 세울 3곳을 선정하고, 3곳이 모두 빈 칸이면 벽을 세우고 바이러스를 퍼뜨린 후, 안전영역의 크기 계산 및 최댓값 갱신을 수행한다. 이때, 3곳의 좌..

[백준 - 14889] 스타트와 링크 [C++]

1. 문제 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 2. 풀이과정 1. n명의 사람을 두 팀으로 나눈다 2. 각 팀의 능력치의 합을 계산한 후 차이를 구한다. 3. 차이의 최솟값을 갱신한다. 1~3을 반복하며 스타트와 링크 팀의 능력치의 차이의 최솟값을 구할 수 있다. [코드설명] stats[i][j]는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. dfs함수는 0번~n-1번 사람들 중 n/2명의 가능한 조합을 구해준다. 예를 들..