BOJ
-
[16197] 두 동전BOJ 2021. 9. 26. 09:51
https://www.acmicpc.net/problem/16197 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net 2개의 동전을 상하좌우로 움직이고, 동전이 한개만 맵을 벗어나게 하기 위한 움직임의 최소 횟수를 구해야한다. 동전은 겹칠 수 있지만, 이경우에는 정답의 가능성이 없다. dfs로 구현할때에 1. depth가 10에 도달한 경우 2. 이미 구한 최적해보다 depth가 커 정답의 가능성이 없는 경우 3. 두개의 동전이 모두 맵을 벗어난 경우 위 3가지일때에는 최적해 업데이트 없이 return 해주었다..
-
[1475] 방 번호BOJ 2021. 9. 26. 09:29
https://www.acmicpc.net/problem/1475 1475번: 방 번호 첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 문자열로 받고, 각각의 수가 등장한 횟수를 카운트해준다. 6과 9는 돌려쓸 수 있으므로, 한번 살때 2개씩 사는것처럼 간주하고, 그외에는 나온 횟수만큼 사야한다. 1. 0~9중 6과 9를 제외한 수가 나온 횟수 2. ceil((6, 9가 나온 횟수)/2) -> 3개면, 2번사야 하므로 올림처리 1,2중 최대값을 출력하면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include using namespace std; int a[..
-
[11050] 이항 계수 1BOJ 2021. 9. 21. 17:20
https://www.acmicpc.net/problem/11050 11050번: 이항 계수 1 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net n과 k가 작아 정의대로 구현해주면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 #include int main(void) { int i,j,n, k,sum=1; scanf("%d %d", &n, &k); if (k > n - k) k = n - k; for (i = n, j = 0; j = 1; i--) { sum /= i; } printf("%d", sum); return 0; } Colored by Color Scripter cs
-
[9466] 텀 프로젝트BOJ 2021. 9. 21. 06:44
https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 프로젝트 팀에 속한 학생의 수를 cnt에 저장하고, (전체 학생수-cnt)를 출력하면 된다. 하나의 사이클을 이루는 경우를 세어야 하는데, 이 부분을 재귀적으로 탐색해나가면 된다. 사이클을 한번 돈 다음에는, 몇개의 노드로 구성된 사이클인지를 판별해야 하고, 사이클 판별여부와 방문진행 여부를 별도로 분리하여 저장하기 위해서 각각 check와 visit이라는 bool형 배열을 만들어서 구현해주었다. 1 ..
-
[1937] 욕심쟁이 판다BOJ 2021. 9. 21. 06:26
https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net bfs를 사용하면 큐가 터진다. dp를 사용한 dfs를 구현해야 500*500의 맵에서도 2초안에 답을 구할 수 있다. dp[i][j] = (i, j)에서 시작했을때의 최적해로 구성해준다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 #include #include ..
-
[2003] 수들의 합 2BOJ 2021. 9. 19. 19:16
https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 최대 10000개의 배열에서 1초안에 투포인터로 합이 m인 경우의수를 세어야한다. 은근히 투포인터랑 비슷한 '느낌'의 알고리즘도 많다. 슬라이딩 윈도우는 len = right-left+1이 항상 일정한 투포인터, 혹은 항상 left++과 right++을 동시에 진행하는 알고리즘이고 토끼와 거북이 알고리즘도 어떻게보면 left와 right의 속도가 다른, 투..
-
[1939] 중량제한BOJ 2021. 9. 17. 10:04
https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 양방향 그래프가 들어오고, 중량이 간선의 가중치보다 낮아야 이동이 가능할때 중량의 최대값을 구하는 문제다. 가능한 중량C가 1~10억이여서 중량 C에 대해서 이분탐색을 진행해주어야 한다. bfs로 중량C에 대해서 정답의 가능성이 있는지를 판별한다. bool을 리턴하도록 구성해주었고 true가 리턴되면 중량C를 운송이 가능하다는 의미이므로 ..
-
[14502] 연구소BOJ 2021. 9. 15. 16:46
https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 결론적으론 브루트포스, 시간내에 해결할 수 있는지 생각해보자. 맵의 최대크기는 8*8, 64칸이다. 여기에 빈칸중 일부를 선택해서 벽을 세워야 하므로, 빈칸의 최대개수도 구해봐야한다. 빈칸의 최대개수는 64-2(바이러스의 최소개수) = 62개이다. 이중 3개를 선택하면, (62*61*60) / 3! 이다. 대략 60*60*10=36000번 정도의 연산횟수로 벽을 세울 수 있다. 벽을 세울 수 있는 경우의 수는..
-
[1759] 암호 만들기BOJ 2021. 9. 13. 18:24
https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net N과 M문제와 매우 유사한 문제다. 완전탐색(백트래킹)으로 해결할 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 #include #include using namespace std; int m, n; int a[20], b[20]; bool che..
-
[1197] 최소 스패닝 트리BOJ 2021. 9. 13. 18:20
https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net MST 기본문제, 크루스칼이나 프림을 구현하면 해결할 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 #include #include #include..