Jubil의 프로그래밍 블로그

1919_애너그램 만들기 링크 https://www.acmicpc.net/problem/1919 풀이 애너그램은 철자를 굉장히 중요하게 생각합니다. 그렇기 때문에 영단어를 철자로 나누어 기록합니다. 그 후, 소문자만 들어오기 때문에 a~z까지 서로 얼마나 차이나나 구하면 제거해야 하는 최소 개수의 문자 수가 나옵니다. 차이를 구하는 방법은 max에서 min을 빼면 됩니다. 코드

3015_오아시스 재결합 링크 https://www.acmicpc.net/problem/3015 풀이 우선 스택을 사용해서 사람들을 내림차순으로 나열하고(같은 수도 포함), 이전보다 더 큰 수가 들어오면 스택을 지워나가며 ans를 구합니다. 다 끝나고 스택에 남아있는 내림차순 사람들을 지워나가며(1명 남기고) ans에 더해줍니다. 지울 때가 중요한데요. 내림차순 도중 더 큰 게 들어오면 이렇게 지워질 때 자신의 양쪽을 볼 수 있으니 ans에 2씩 더해주면 됩니다. 하지만 자신이 맨 왼쪽이었다면 왼쪽을 볼 수 없으니 ans에 1을 더해주면 됩니다. 그리고 같을 때가 문제인데요. 같은 키를 가진 사람들끼리 볼 수 있는 인원 + 같은 키를 가진 사람들이 볼 수 있는 왼쪽 오른쪽 사람을 더해주면 됩니다. 가운데..

6549_히스토그램에서 가장 큰 직사각형 링크 https://www.acmicpc.net/problem/6549 풀이 이 문제는 스택을 이용해서 풀 수 있는 문제입니다. 각 칸에서 왼쪽과 오른쪽으로 각각 어느 칸까지 뻗어 나갈 수 있는지 구하고, 그 길이 * 높이를 곱해서 가장 큰 크기를 선택하면 답이 나오고, 시간 복잡도는 3n, O(n)이 됩니다. 왼쪽으로 뻗어 나갈 수 있는 정도를 구하는 방법은 0번지부터 n-1번지까지 스택에 오름차순 정렬을 하는 것인데요. 높이가 같을 때도 스택에서 pop 해줘야 합니다. 그렇게 되면 스택 안에 있는 번지들은 i번째(현재 고려하는 칸)에서 왼쪽으로 뻗어 나갔을 때, 만나게 되는 장애물들을 나타내게 됩니다. i번째의 높이가 스택의 top번째의 높이보다 높다면 왼쪽으..

2493_탑 링크 https://www.acmicpc.net/problem/2493 풀이 각 레이저가 왼쪽으로 얼마나 뻗을 수 있는지 체크하기 위해서 스택을 사용해 풀 수 있습니다. 이 문제에서는 내림차순 스택을 사용하면 되는데요. 시작을 1번지라고 두고 1번지부터 n번지까지 스택에 내림차순을 유지하면서 집어넣는 것입니다. 스택 내부의 번지들은 현재 i번째 탑이 발사한 레이저 신호를 수신할 가능성이 있는 탑을 의미합니다. i번째 탑의 높이가 바로 스택의 top번째 탑의 높이보다 작거나 같다면 발사한 레이저는 바로 왼쪽 탑이 수신할 것이므로 left[i]는 top이 됩니다. 그리고 이제 i번째 탑이 수신할 가능성이 제일 높으니 i를 push합니다. i번째 탑의 높이가 스택의 top번째 탑의 높이보다 크다면..

16204_카드 뽑기 링크 https://www.acmicpc.net/problem/16204 풀이 O가 적혀 있는 카드가 M개, 내가 O를 적은 카드가 K개라고 한다면, K가 M보다 많을 때 M개 맞힐 수 있고, 그렇지 않을 때는 K개 맞힐 수 있습니다. 따라서 min(K, M)이죠. 그리고 X가 적혀 있는 카드가 N-M개, 내가 X를 적은 카드가 N-K개일 테니 마찬가지로 min(N-M, N-K)입니다. 둘을 더해주면 답이 됩니다. 코드

2355_시그마링크https://www.acmicpc.net/problem/2355 풀이 처음에 부호 고려해서 상쇄되는 부분 잘라내고 했는데, 그냥 long long으로 두고 n(a+l)/2로도 풀리는 문제였습니다. 첫째 항과 마지막 항은 대소비교로 결정하고, n은 등차가 1이고 A와 B를 포함하기 때문에 큰 수 – 작은 수 + 1로 해주시면 됩니다. 코드

1297_TV 크기 링크 https://www.acmicpc.net/problem/1297 풀이 너비 높이 비율을 이용해서 피타고라스로 대각선 비율 구하고, 대각선 비율과 실제 대각선 길이를 비교하여 너비와 높이를 찾아내면 됩니다. 코드

9506_약수들의 합 링크 https://www.acmicpc.net/problem/9506 풀이 자신을 제외한 약수를 반복문으로 구한 뒤 더해서 완전수이면 약수들의 합으로 나타내어 출력합니다. 완전수인지 판별, 출력 이렇게 반복문 두 번 돌려주시면 됩니다. 코드

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)