본문 바로가기
반응형

백준18

[cpp 알고리즘] 백준 4396 지뢰 찾기 [백준] 4396 지뢰 찾기 cpp 풀이알고리즘: 구현https://www.acmicpc.net/problem/4396 문제 요약 N*N의 지뢰 판이 주어지고, M개의 지뢰가 있다. - 입력1) 온점(.)은 지뢰가 없고, 별표(*)는 지뢰가 있는 지점이다.- 입력2) 이미 열린 칸은 영소문자x로, 열리지 않은 칸은 온점(.)으로 표시된다. - 출력) (1) 지뢰가 없으면서 열린 칸은 0~8 사이의 숫자, (2) 지뢰가 있는 칸이 열렸으면 지뢰가 있는 모든 칸을 별표(*)로, (3) 다른 모든 지점은 온점(.) 으로 표현해야 한다. 문제를 이해하는 것과 주어진 테스트코드로 이해는 쉬웠으나, 몇 가지 경우에 대해 더 생각해 봐야 한다...😒풀이 정리(1) 우선 N*N의 기본 지뢰 판을 만들고, 온점(.)과.. 2024. 7. 8.
[cpp 알고리즘] 백준 17291 새끼치기 [백준] 17291 새끼치기 cpp 풀이알고리즘: 구현, 다이나믹 프로그래밍(DP)https://www.acmicpc.net/problem/17291문제 요약아래의 벌레 분열 규칙만 고려해서 코드를 풀이하면 된다.  벌레는 기준년도 1년 2월에 1마리가 탄생한다.벌레는 매년 1월이 되면 분열한다. 분열시 본래의 개체는 그대로, 새로운 개체가 하나 탄생하는 것으로 본다.홀수년도에 탄생한 개체는 3번 분열시, 짝수년도에 탄생한 개체는 4번 분열시 사망한다.이 때, N년 말에 존재하는 벌레의 수를 구하면 된다. 풀이 정리- 기준년도 1년 2월 = 1 마리- 2년 1월 = 1 + 1(새로 분열)- 3년 1월 = 1 + 1 + 2(새로 분열) - 4년 1월 = 1 + 1 + 2 + 4(새로 분열) - 1(기준년도.. 2024. 7. 7.
[cpp 알고리즘] 백준 1629 곱셈 [백준] 1629 곱셈 cpp 풀이 수학, 분할 정복을 이용한 거듭제곱 https://www.acmicpc.net/problem/1629 문제 요약 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어졌을 때, A를 B번 곱한 수를 C로 나눈 나머지를 출력하면 된다. 풀이 정리 - 분할 정복을 활용하여 지수를 나누어 주면 된다. (1) 지수가 0인 경우 -> X^0 = 1 이므로 1을 리턴해준다. (2) 지수가 짝수인 경우 -> X를 X/2로 나누어서, 계산한 두 값을 곱해준다. (3) 지수가 홀수인 경우 -> X를 X/2로 나누고, 계산한 두 값과 밑을 한 번 더 곱해준다. - 예제에 나왔던 A=10, B=11로 예를 들어 보면, 1. 가장 나이브하게 먼저 생각나는 방법은 for문을 이용하여 .. 2023. 11. 10.
[cpp 알고리즘] 백준 1780 종이의 개수 [백준] 1780 종이의 개수 cpp 풀이분할정복, 재귀https://www.acmicpc.net/problem/1780 문제 요약N(1 ≤ N ≤ 37, N은 3k 꼴) * N 크기의 행렬로 표현되는 종이에서, 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. - 만약 종이가 모두 같은 수라면, 그대로 사용한다. - 아니라면, 종이를 같은 크기의 종이 9개로 자르고, 각각의 종이에 대해서 위의 과정을 반복한다. 출력값으로, 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구하면 된다. 풀이 정리이전에 진행한 분할정복 문제와 같다. 즉 구간을 나눠가면서, (1) N=1인지 확인하기, (2) 그 부분이 모두 같은 값으로 이루어져있는지 확인하기.. 2023. 11. 9.
반응형

티스토리툴바