Jubil의 프로그래밍 블로그

1629_곱셈 링크 https://www.acmicpc.net/problem/1629 풀이 b가 21억까지기 때문에 곱하고 나머지 구하기를 반복하다 보면 시간을 초과하게 됩니다. 그래서 지수법칙을 이용하기로 했습니다. 제곱한 걸 다시 제곱하면 네 제곱이 되고 또 제곱하면 여덟 제곱이 되는 것을 이용하는 것입니다. 아홉 제곱을 구하기 위해서는 첫 번째 수 a를 다시 곱하면 됩니다. 이렇게 제곱과 첫 번째 수를 곱함으로써 b 제곱을 만들면 됩니다. 하지만 그 방법은 다운탑이므로 탑다운으로 과정을 구하고 난 후 쌓아 올려줍니다. 이런 방식으로 코드를 짜면 log2n으로 구할 수 있겠네요. 코드

1964_오각형, 오각형, 오각형… 링크 https://www.acmicpc.net/problem/1964 풀이 단계마다 더 추가되는 점들에 집중하면 됩니다. 우선 1단계에서 5개가 추가됩니다. 그리고 그 단계에서는 동그라미로 표현한 꼭짓점 4개와 그 사이 3개의 변에 n-1 단계만큼의 점이 추가됩니다. 즉, 수식으로 표현하면 3*(n-1)

2864_5와 6의 차이 링크 https://www.acmicpc.net/problem/2864 풀이 모든 6을 5로 헷갈렸을 때 최솟값을, 모든 5를 6으로 헷갈렸을 때 최댓값을 갖습니다. A와 B가 양수이기 때문이죠. 문자열 변환만 잘 처리해주면 됩니다. 코드

1100_하얀 칸 링크 https://www.acmicpc.net/problem/1100 풀이 8*8의 체스판을 입력 받으면서 i%2가 0일 때, j%2도 0이면 하얀 칸, i%2가 1일 때, j%2도 1이면 하얀 칸이라는 것을 이용해서 풀면 됩니다. 코드

1076_저항 링크 https://www.acmicpc.net/problem/1076 풀이 세 색을 각각의 값으로 변환해줍니다. 그리고 앞의 두 값을 first*10 + second 한 후 10^third를 곱해주면 됩니다. 코드

1075_나누기 링크 https://www.acmicpc.net/problem/1075 풀이 뒤 두 자리를 적절히 바꿔서 나누어 떨어지게 만든다. 가능한 것이 여러 가지면, 뒤 두자리를 가능하면 작게 만드려고 한다. (가능한 경우가 없을 경우는 나와있지 않으니 고려하지 않겠습니다.) 위의 두 가지 경우를 생각해보면, 정수가 주어졌을 때 뒤의 두 정수를 떼어내고 0부터 99까지 더해서 나누어 떨어질 경우 stop한 다음 조건에 맞게 출력해주면 됩니다. 조건은 앞에 0을 채워서 출력하는 것입니다. 두 정수를 떼어내는 방법은 100으로 나누고 다시 100을 곱하거나, 나머지 연산으로 100한 것을 빼면 됩니다. 0을 채워서 출력하는 것은 printf에서 %02d를 사용하면 됩니다. 코드

1012_유기농 배추 링크 https://www.acmicpc.net/problem/1012 풀이 문제는 최소의 배추흰지렁이 마리 수를 요구합니다. 배추흰지렁이는 상하좌우 네 방향으로만 생각해야하기 때문에 dx배열과 dy배열을 만들어줍니다. 땅을 배열로 표현한 다음 배추가 있는 곳을 1이라 해놓고 dfs를 돌리면 풀 수 있습니다. 코드

11497_통나무 건너뛰기 링크 https://www.acmicpc.net/problem/11497 풀이 통나무 건너뛰기의 최소 난이도를 구하는 문제입니다. 난이도는 인접한 통나무의 높이차의 최댓값으로 결정됩니다. 그렇다면 어떻게 통나무를 배열해야 가장 작은 높이차를 만들 수 있을까요? 통나무의 높이를 내림차순으로 정렬한 후, 가장 큰 값을 가운데에 두고 왼쪽 오른쪽 번갈아 가면서 놓으면 됩니다. 왼쪽 오른쪽 번갈아 놓기 때문에 중간에서의 높이차는 2칸 떨어진 통나무의 높이차가 될 것이고, 예외로 연결되는 통나무인 첫 번째와 마지막 번째 통나무의 높이차가 1칸 떨어진 통나무의 높이차가 더 추가됩니다. 그렇게 해서 max 값을 구해주면 그 통나무 건너뛰기의 난이도가 됩니다. 코드

15553_난로 링크 https://www.acmicpc.net/problem/15553 풀이 친구들은 집에 1초씩 있다가 나갑니다. 친구들이 오고 가고 하는 동안 난로를 끄고 켜고 하는 것을 다 고려하긴 좀 힘듭니다. 그렇다면 어떻게 쉽게 풀 수 있을까요? 우선 처음 친구가 방문한 시간과 마지막 친구가 나간 시간의 차이를 구합니다. 이 시간은 난로를 친구가 방문했을 때부터 마지막 친구가 나갈 때까지 계속 켜고 있는 상황입니다. 그리고 친구가 방문하지 않는 시간(뒤 친구가 방문한 시간 – 앞 친구가 나간 시간)들을 priority queue에 넣고 k-1개만큼 빼줍니다. 성냥으로 다시 난로를 켤 수 있기 때문에 방문하지 않는 시간을 가장 긴 시간부터 절약하는 것이죠. 그러면 답을 구할 수 있습니다. 코드

1057_토너먼트 링크 https://www.acmicpc.net/problem/1057 풀이 토너먼트이기 때문에 8과 9를 2로 나누면 동일한 4를 갖는 성질을 이용해서 풀 수 있습니다. 만약 1, 2, 3 3명이 경기를 할 때, n인 3+1을 2로 나누면 부전승 포함 2명이 남고, 1+1과 2+1을 2로 나누면 둘의 승자는 1이라는, 3+1을 2로 나누면 2라는 번호가 부여됩니다. 저 상황에서 1과 2가 김지민과 임한수라면 둘 다 1을 더하고 2로 나눴을 때, 같은 값을 가진다면 그때 상대와 붙는 것입니다. 그래서 결론은 1을 더하고 2로 나누는 방식으로 n(인원수), 김지민의 번호, 임한수의 번호를 제어해서 언제 대결하는지 파악하면 됩니다. 마지막에 대결하지 않는 경우가 나오는데, 둘 다 서로 대결..