https://www.acmicpc.net/problem/19590 19590번: 비드맨 구슬을 엄청 좋아하는 비드맨이 있다. 구슬만 보면 갖고 싶어 하는 비드맨은 오늘도 갖고 싶은 구슬을 발견했다. 그러나 비드맨은 현재 구슬을 너무 많이 갖고 있기 때문에 더 이상 구슬을 가질 www.acmicpc.net 1. 최댓값 > 나머지의 총합인 경우 - 싹 다 최댓값이랑 부딪히면 된다. 따라서 답은 최댓값 - 나머지의 합 2. 최댓값 >TEST_CASE;for(int TEST_NUM=1;TEST_NUM> x; #define sc2(x,y) int x,y;cin>>x>>y #define sc3(x,y,z) int x,y,z;cin>>x>>y>>z #define sc4(x,y,z,w) int x,y,z,w;cin>..
https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표 www.acmicpc.net https://www.acmicpc.net/problem/2636 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진�� www.acmicpc.net 매우매우 비슷한 문제 차이가 있다면 치즈가 녹을 조건이 공기와 맞닿은 칸이 2칸 이..
https://www.acmicpc.net/problem/19235 19235번: 모노미노도미노 모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, www.acmicpc.net 구현문제 문제의 조건을 차근차근 살펴보자. 블럭은 이렇게 총 세종류가 있다. 블럭을 빨간색에 위치시키면 다음과 같이 배치된다. 1 x 2 블록을 다시한번 배치했을 때에는 다음과 같은 모양이 된다. 여기서 녹색보드의 (4, 0)부분에 블록이 걸쳐있는 것으로 보아 블록이 걸칠 경우 분리되어 떨어지지 않는다는 것을 볼 수 있다. 초록색보드의 4번 행을보면 한줄이 모두 채워져 있음을 확인할 수 있..
https://www.acmicpc.net/problem/11867 11867번: 박스 나누기 게임 첫째 줄에 N과 M이 주어진다. (1 ≤ N, M ≤ 100, N과 M이 모두 1인 경우는 없다) www.acmicpc.net 신나는 게임이론 공책에 좀 끄적이다보니 규칙이 보였다. 두 상자중 한 상자라도 2개짜리가 존재한다면 1, 1 로만들 수 있으니 승리할 것이다. 3개짜리의 상자는 1, 2로 밖에 만들 수 없으므로 패배할 수 밖에 없다. 이걸 토대로 규칙을 찾아보도록 하자. 4개 -> (1, 3), (2, 2) 2, 2로 나눌 경우 항상 승리하므로 4개짜리 상자는 승리를 가져다준다. 5개 -> (1, 4), (2, 3) 어떻게 나누어도 상대가 승리할 수 밖에없다. 첫번째 경우에는 위에서 구한대로 4개..
https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모�� www.acmicpc.net 요놈도 문제가 길다. 마찬가지로 BFS + 구현 문제이다. BFS를 통해서 갈 수 있는 나라끼리는 연합이 될 수 있으므로 방문이 안된 국가들에 대해 bfs를 돌려 서로 방문할 수 있는 국가들끼리 인구수를 더해 똑같이 분배해주도록하자. 더이상 국경선이 열릴 수 없을 때에 답을 출력해주면 되겠다. 아래는 소스코드이다. 더보기 #include #define endl '\n' #defi..
https://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 문제가 워낙 기니 문제 설명은 링크를 가서 읽어주시길.. 문제를 보면 알겠지만 딱 BFS 구현문제다. 개인적으로는 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존..
https://www.acmicpc.net/problem/9660 9660번: 돌 게임 6 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1,000,000,000,000) www.acmicpc.net 백준에는 돌 게임이 참 많다. 이 문제는 solved.ac 기준으로 골드5의 난이도를 가지고 있는데 실버에 속한 돌 게임과의 차이점은 N의 범위가 굉장히 크다는 것이다. 따라서 O(N)의 풀이조차도 TLE가 발생한다. 이런 게임이론 같은 경우에는 규칙을 찾아 푸는 것이 가장 편한 방법인 듯하다. 못찾으면 난이도가 급상승하니.. 수학적으로 머리가 비상해서 규칙만 읽고 규칙을 찾을수만 있다면 정말 좋겠지만 필자는 똑똑이가 아니라서 적당한 탐색을 통해 규칙을 찾기로 했다. 우선 돌이 1~4개 있을 때를 생각해보자. ..
https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부� www.acmicpc.net 작업의 우선순위가 주어지고 특정 작업을 수행하기 위해서는 그 작업보다 먼저 수행되어야하는 작업들이 모두 완료되어야한다. 이 문제와 마찬가지로 위상 정렬 문제라는 것을 알 수 있다. 하지만 이 문제는 특정 건물을 지을 수 있는 시간을 묻는 것이므로 단순 위상정렬 뿐만이 아닌 구현이 필요하다. 이 그림을 확인해 보자. 건물 1의 경우 10초가 소요 될 것이다. 건물 2와 3의 경우에는 각각 1..