[C++] 백준 1629: 곱셈
문제 이해- 자연수 A를 B번 곱한 수를 구하려고 한다.- 단 매우 커질 수 있으므로 C로 나눠주도록 하자. - 시간 제한: 0.5초- 메모리 제한: 128MB - A: 곱하는 수- B: 곱하는 횟수- C: 나누는 수A, B, C 모두 (1 ~ 2,147,483,647) 사이의 정수로 int형으로 표현할 수 있다. - A를 B번 곱한 수를 C로 나눈 나머지를 출력하자. 문제 풀이처음에 가장 먼저 생각한건 역시 브루트포스다A를 그냥 B번 곱해주는 것이다. 그런데, B의 최댓값은 2,147,483,647로 대략 10^9를 넘는다.즉, O(N)의 시간복잡도를 가져도 시간 초과로 AC를 받을 수 없을 것이다. 도저히 시간 복잡도를 줄일 방법이 생각나지 않아서 인터넷을 참고했다. 이 문제를 푸는 방법은 '..
[C++] 백준 1459: 걷기
문제 이해- 학교에서 집까지 가려고 한다.- 도시의 크기는 무한대이다.- 도로는 수평으로 또는 수직으로 모두 존재한다. -> 수직선을 생각하자.- 세준이의 현재 위치는 (0,0)이다.- 세준이는 가로로 걷거나, 세로로 걷거나, 대각선으로 가로지를 수 있다.- 집까지 가는 최소시간을 구하라. - 시간 제한: 2초- 메모리 제한: 128MB - x, y: 집의 위치 (0 ~ 1,000,000,000, 10^9)- w: 1블록을 가는데 걸리는 시간 (1 ~ 10,000, 10^4)- s: 1블록을 가로지르는데 걸리는 시간 (1 ~ 10,000, 10^4) - 세준이가 집까지 가는데 걸리는 최소시간을 구하라. 문제 풀이시작은 경우의 수를 나눠서 풀어야겠다고 생각했다.세준이는 가로로 이동, 세로로 이동, 대각..
