https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 1. Logic 물에 잠기지 않는 지점이 최대가 될 때를 구하는 문제이다. 처음에 이 문제를 봤을 때 그냥 주변높이 보다 높으면 안전지역인줄 알았는데 문제를 다시 읽어보니 0~최대 높이까지 확인하면서 그중에 가장 많은 안전지역의 갯수를 구하는 문제이다. 풀이 방법은 입력을 받으면서 최대 높이를 구하고 0~최대 높이 까지 BFS를 돌면서 최대 안전 지역의 갯수를 구하면 된다. 2. Code #include..
알고리즘
https://www.acmicpc.net/problem/3015 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net 1. Logic 1. pair를 원소로 가지는 stack 하나를 선언한다. pair는 이다. 2. 현재 입력받은 키보다 작은 애들은 무조건 볼 수 있기 때문에 pairCnt를 올려주고 어짜피 나보다 작은애들이기 때문에 나보다 큰 애가 들어오게 되면 내 뒤의 작은애는 보지 못하기때문에 스택에서 pop해주고 다시 넣어주지 않는다. > 이 방식으로 스택을 항상 내림차순으로 정렬해..
https://www.acmicpc.net/problem/1244 1244번: 스위치 켜고 끄기 첫째 줄에는 스위치 개수가 주어진다. 스위치 개수는 100 이하인 양의 정수이다. 둘째 줄에는 각 스위치의 상태가 주어진다. 켜져 있으면 1, 꺼져있으면 0이라고 표시하고 사이에 빈칸이 하나씩 www.acmicpc.net 1. Logic 남학생은 배로수 바꿔주면 쉽지만 여학생이 문제이다. 여학생이 받은 번호 기준으로 왼쪽 오른쪽이 같으면 바꿔주고 다르면 바꿔주면 안된다. 그래서 while문의 조건을 swit[start] == swit[end]로 잡아줬다. 그리고 20개마다 줄 바꿔주는것을 잘 신경쓰면 된다! 2. Code #include using namespace std; int n, m; bool swit..
https://www.acmicpc.net/problem/25757 25757번: 임스와 함께하는 미니게임 첫 번째 줄에는 사람들이 임스와 같이 플레이하기를 신청한 횟수 $N$과 같이 플레이할 게임의 종류가 주어진다. $(1 \le N \le 100\,000)$ 두 번째 줄부터 $N$개의 줄에는 같이 플레이하고자 하는 사람들 www.acmicpc.net 1. Logic 임스와 lms는 다른 사람이라는거에 유의해서 입력을 받고 Map에 없으면 카운트해주고 있으면 넘어가준다. 코드를 보면 쉽게 이해가 갈 것이다. 2. Code #include using namespace std; map name; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cou..
https://www.acmicpc.net/problem/4673 4673번: 셀프 넘버 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, www.acmicpc.net 1. Logic - check배열을 만들어서 리턴된 수는 생성자가 있는 숫자이기 때문에 체크를 해서 check배열이 true인 숫자들만 출력해주면 된다. 2. Code #include using namespace std; bool check[10001]; int cur(int num) { int sum = num; while(num != 0) { ..
https://www.acmicpc.net/problem/17484 17484번: 진우의 달 여행 (Small) 첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2≤ N, M ≤ 6)이 주어진다. 다음 N줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소값은 100 이하의 자연수이다. www.acmicpc.net 1. Logic 브루트 포스로 풀 수 있지만 각 칸에서의 최솟값은 변하지 않기 때문에 그 값을 저장해 놓고 DP로 풀이할 수 있다. 2. Code #include using namespace std; int n, m; int space[10][10]; int dp[10][10][4]; //0:왼 1:dir 2:오 int solve(int y, int x, int p..
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 1. Logic 다리가 버틸 수 있는 무게가 10억까지이기 때문에 택배의 무게를 이분탐색으로 찾아준다. 이분탐색의 Check함수는 택배의 무게인 mid보다 각 경로가 버틸 수 있는 무게가 크거나 같을 때만 통과시켜 입력받은 출발지에서 시작하여 도착지에 도달할 수 있으면 택배의 무게를 늘리고 도착하지 못하면 택배의 무게를 줄이면서 적절한 택..
https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 1. Logic 이 문제에서 mid값은 공유기와 공유기 사이의 거리를 뜻한다. 이분탐색으로 공유기와 공유기 사이의 거리를 구한 후 wifi[0]~wifi[n-1]까지 탐색하며 공유기간의 사이가 mid보다 큰거나 같을 때를 count해주며 count가 공유기 설치대수 m보다 크거나 같으면 start를 mid로 옮겨, 작으면 end를 mid로 옮겨 ..
https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 1. Logic 이 문제에서는 이분탐색으로 찾으려는 mid값이 무엇인지를 정하는게 중요하다고 생각한다. 내가 정한 mid값은 블루레이의 길이이다. 강의 영상의 순서대로 블루레이에 넣어야되기 때문에 이분탐색의 check()함수는 블루레이에 순서대로 영상이 들어가는지 판단해주면 된다. 우리가 찾는 mid값은 가능한 값들중에 최솟값이기 때문에 가능한 mid값의 구간은 FFFF[FT]TTTT가 된다. 그중 가능..
https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 www.acmicpc.net 1. Logic 문제 요약 : 톱니바퀴와 맞닿아있는 톱니가 다른 극이면 톱니를 반대방향으로 움직이고 같은 극이면 톱니를 움직이지 않는다. 각 톱니별 부분 문제를 생각해보자면 회전방향 \ 톱니번호 1번 톱니 2번 톱니 3번 톱니 4번 톱니 시계방향 2번 > 반시계 3번 > 시계 4번 > 반시계 1번 > 반시계 3번 > 반시계 4번 > 시계 1번 > 시계 2번 > 반시계 4번 > 반시계 1번 >..
