코딩하는 맏리믓

문제 https://www.acmicpc.net/problem/22251 22251번: 빌런 호석 LED를 2개까지 바꿀 수 있을 때, 5층에서 3층, 6층, 8층, 그리고 9층으로 바꿔버릴 수 있다. www.acmicpc.net 문제 해석 - N(최대 층수), K(표기 자릿수), P(최대 변경 가능 횟수), X(현재 층수) 가 주어진다. - 이 때 현재 층수 K 를 최대 변경 가능 횟수인 P 만큼 변경해 몇개의 다른 숫자로 변경 가능 한지 찾아내면 되는 문제이다. 문제 풀이 - 우선 전자시계식 숫자는 사람은 알아 보기 쉽지만 컴퓨터는 판별이 어려우니 이를 배열화 하여 저장 하여야 한다. . 이를테면 0 -> 1, 1, 1, 0, 1, 1, 1 이런 식으로 표시등 7개에 번호를 붙여 점등시 1 아닐시 0..

문제 https://www.acmicpc.net/problem/1863 1863번: 스카이라인 쉬운거 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 50,000) 다음 n개의 줄에는 왼쪽부터 스카이라인을 보아 갈 때 스카이라인의 고도가 바뀌는 지점의 좌표 x와 y가 주어진다. (1 ≤ x ≤ 1,000,000. 0 ≤ y ≤ 500,000) 첫 www.acmicpc.net 문제 해석 - 밤에 태양이 질 때 보이는 건물의 윤곽을 스카이 라인이라 한다. - 이 스카이 라인을 보고 건물이 최소 몇개 있는지 구하는 문제이다. - 예시로 아래처럼 윤곽이 보인다면 건물이 3개 존재 하는데 다음과 같다. .......... .....XX... .XXX.XX... XXXXXXXXXX .......... .....XX.....

문제 https://www.acmicpc.net/problem/7682 7682번: 틱택토 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 줄은 9개의 문자를 포함하며, 'X', 'O', '.' 중 하나이다. '.'은 빈칸을 의미하며, 9개의 문자는 게임판에서 제일 윗 줄 왼쪽부터의 순서이다. 입 www.acmicpc.net 문제 해석 - 입력값으로 3*3 의 게임 판에 O, X 를 표기하여 주어진다. - 주어진 게임판의 상황이 나올 수 있는 상황인지, 끝난 상황인지 확인 하는 문제이다. - 예를 들어 "X.OO..X.." 는 나올 수는 있는 상황이지만 게임의 최동 모습이 아니기 때문에 "invalid" 이다. 문제 풀이 - 게임이 정상적으로 끝났다면 다음 상황 중 하나이다. . O 를 표기 한 사..

문제 https://www.acmicpc.net/problem/24042 24042번: 횡단보도 당신은 집으로 가는 도중 복잡한 교차로를 만났다! 이 교차로에는 사람이 지나갈 수 있는 $N$ 개의 지역이 있고 그 지역 사이를 잇는 몇 개의 횡단보도가 있다. 모든 지역은 횡단보도를 통해 직, www.acmicpc.net 문제 해석 - 일반적인 최단거리와는 조금 다른 문제라고 보면 된다. - 최단거리를 구하는 문제는 가중치가 고정 되어 있지만 이 문제는 시간이 지남에 따라 가중치가 계속 변화 하기 때문이다. - 변하는 가중치에 따라 첫 위치부터 끝지점까지 가는 최소 시간을 구하면 되는 문제이다. 문제 풀이 - 여기서 신경 써야 할 점은 시간이다. . 만약 3번 위치까지 4의 시간안에 갔는데 3->4 신호등이..

문제 문제 해석 - 입력으로 1과 0이 2차원으로 들어 온다. - 받은 입력에서 서로 붙어 있는 1을 하나의 단지라고 본다. - 이때 단지의 개수와 해당 단지에 1이 몇개 있는지 세어서 출력 하면 되는 문제이다. 알고리즘 - 그래프와 dfs 를 사용 하면 된다. - 방문한 집을 표시하기 위한 visit 배열과 집의 위치를 담은 home 배열을 만든 후 집의 위치를 입력 받는다. - home 배열을 탐색 하다 집이 있는 위치에서 부터 해당 집과 연결된 모든 집은 탐색하며 단지의 수를 세어 준다. - 방법은 다른 그래프 탐색 방법과 동일하게 진행 해 주면 된다. - 자세한 방법은 코드에서 설명 하도록 하겠다. - 세어준 단지 수는 vector 에 저장 해 주고 이후에 벡터의 size 와 정렬된 벡터를 출력 ..

문제 문제 해석 - 색종이를 종이 내에 같은 색만이 남을 때 까지 1/4로 계속 잘랐을 때 휜색과 파란색 정사각형 종이가 몇장씩 있는지 알아내는 문제이다. 알고리즘 - 재귀를 통한 분할정복으로 문제를 해결 하면 된다. - 종이의 시작 좌표와 크기를 넘겨 받은 후 해당 종이의 색이 같은지를 확인한다. - 이때 하나라도 다른 색이 끼여 있다면 종이를 4등분 하여 같은 동작을 반복 한다. - 방법은 4등분 한 종이의 시작 좌표(가장 좌측 상단의 x, y 좌표)와 자른 후의 size 를 재귀함수에 넘겨 주면 된다. - 모든 색이 같다면 무슨색인지 조사하여 해당 색의 종이 수를 하나 늘려 준다. 코드 #include using namespace std; int paper[130][130]; int blue=0, ..

문제 문제 해석 - 숫자 3과 5를 최소한으로 사용하여 더해 주어지는 수 N 을 만들어 주면 되는 문제이다. 알고리즘 - DP 알고리즘을 사용하면 간단하게 해결 할 수 있다. - 우선 무게가 3, 5인 경우에는 각 3kg, 5kg 봉지 하나씩 을 사용 하면 된다. - 이 경우 DP[3] -> 1, DP[5] -> 1 가 되게 된다. - 여기서 부터 시작 하여 무게가 i 일 경우에 DP[i-3] 이 만들 수 있다면 DP[i] = DP[i-3] +1이 된다. - 그 이유는 DP[i-3] 에서 3kg 하나만 추가 하면되기 때문이다. - 만약 DP[i-5] 가 존재 할 때는 같은 원리로 DP[i] = DP[i-5]+1 이 된다. - 이때 주의 해야 할 점은 i 가 '8' 같은 경우이다. - 이 경우에는 '8 -..

문제 문제 해석 - 주어진 카드중 3장을 뽑아서 더했을 때 문제에서 주어진 M 을 넘지 않으면서 가장 큰 수를 찾으면 되는 문제이다. 알고리즘 - 생각 보다 시간이 넉넉 하기 때문에 모든 경우의 수를 다 돌려 가며 가장 큰 수를 찾으면 된다. - 카드 3장을 찾아야 하기 때문에 3중 for 를 돌면서 3장을 골라주고 이를 더해 M 을 넘지 않는 수를 찾아 주면 되는 간단한 문제이다. 코드 #include #include using namespace std; int N, M; vector card; int main(){ cin >> N >> M; for(int i = 0; i > tmp; card.push_back(tmp); } int sum = -1; ..

문제 문제 해석 - 입력 받은 수의 팩토리얼가 뒤에 0이 몇개 붙는지를 세면 되는 문제이다. 알고리즘 - 곱에서 뒷자리가 0이 나오는 경우는 2의 배수와 5의 배수가 곱해지는 경우이다. - 팩토리얼은 1부터 순서대로 곱하기 때문에 5의 배수가 곱해 질 때는 항상 짝수와 곱해진다. - 이때 주의 할 점은 25, 125 처럼 5의 제곱수가 곱해질 때는 5가 2번 3번 곱해질 때는 0 또한 2개, 3개가 붙는다. - 정리하면 숫자 N 이 주어 졌을 때 1 ~ N 까지 하나씩 증가 시키며 - 5의 배수가 나올 때 마다 0이 하나씩 - 25의 배수가 나올 때 마다 0이 두개씩 - 125의 배수가 나올 때 마가 0이 세개씩 붙게 된다. - 이를 모두 count 해 주면 뒤에 붙는 0의 총 개수가 나오게 된다. 코드..

문제 문제 해석 - 문자열(포켓몬 이름) 을 입력 받는다. - 그 후 이름이 나오면 그 포켓몬이 몇번째 입력 받은 것인지 - 숫자가 나오면 그 번째 에 어떤 포켓몬이 입력 받았었는지 출력 하면 되는 문제이다. 알고리즘 - 포켓몬 이름을 입력 받을 때 숫자로 탐색 하기 위한 vector 와 이름으로 탐색 하기 위한 map 을 따로 만들어 동시에 받아 준다. - 이 후 문제를 입력 받는데 숫자로 입력 되었다면 첫글자가 숫자 일 테니까 문자열로 입력 받은 후 첫 글자의 아스키 코드가 48 ~ 57 사이면 된다. - 만약 숫자라면 입력 받은 문자열을 숫자로 변경 해 주고 vector 를 통해 이름을 검색 한다. - 숫자가 아니라면 해당 문자를 map 을 통해 검색 하면 된다. - 이때 찾을 때 마다 cout 으..