취미겸생업

https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 문제분석 예전에 한 번 풀어본 적 있다 원판의 갯수 : N 원판이 한개, 두개, 세개, 네개일 때의 경우를 보고 패턴을 파악했던 것 같다 일단 횟수는 1번, 3번, 7번, 15번, 31번, …, (n-1)*2 + 1이다 횟수 : count(N-1)*2 + 1 이는 원판 이동이 총 세 단계로 이뤄진다는 뜻이다 (N-1) 번째 이하의 모든 원판을 두 번째 장대로 옮긴다 (이동횟수 : co..

https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 문제분석 모든 변수의 범위가 int형이라 long long int로 대충 계산해도 오버플로우가 난다 전혀 감을 못잡겠어서 강의 보았다 아무리 봐도 이해가 안돼서 찾아봤는데 모듈러 연산 공식을 사용함 모듈러 연산에 대해 알고 있어야 강의도 이해할 수 있음 ≡ : 모듈러 합동 3(mod 67) : (mod 67)의 3번째 사이클 ex) 11^12 mod 13 → 11^2 mod 13 = 121 ≡ 4 (mod 13) → 11^4 mod 13 = (11^2)^2 ≡ ..

https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 문제분석 (0,0) ~ (n,m) 까지의 최단거리 문제이다 → BFS로 거리를 잰다 BFS로 탐색만 해봤는데 거리를 재는 건 다른 문제다 보니 생각이 필요할 것 같다 알고리즘 #include #include #include int main(void){ std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); int n, m; std::c..

https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 문제분석 이어져 있는 1을 그림 하나로 친다 → 이어져 있는 1의 개수를 구하는 게 핵심 (0, 0) ~ (n, m) 까지 검사한다 → (x, y) 를 현재 넓이를 검사 중인 그림의 한 cell이라고 보았을 때 이 cell을 기준으로 상하좌우 검사하며 이어져 있는 1의 개수를 구한다 검사를 시작하는 cell은 중복될 수 있으므로 특정 그림의 일부분으로 검사를 마친 cell은 다시 검사하지 않는다 그림의..