Jubil의 프로그래밍 블로그

1712_손익분기점 링크 https://www.acmicpc.net/problem/1712 풀이 손익분기점을 찾으려면 다음과 같은 식을 세울 수 있습니다. a + b*ans = c인 경우입니다. 똑같이 팔거나 손해가 나면 손익분기점이 없겠죠? 코드

2903_중앙 이동 알고리즘 링크 https://www.acmicpc.net/problem/2903 풀이 너무 깊게 생각하지 말고 점이 일정한 간격을 두고 채워져 있기 때문에 점을 이용해서 면적을 구한다고 생각해봅시다. 사각형들은 정사각형이기 때문에 가로와 세로가 같습니다. 첫 번째 사각형의 가로의 점은 2개가 있습니다. 넓이를 구한다고 생각하고 제곱을 하면 4가 되죠. 두 번째 사각형의 가로의 점은 3개가 있습니다. 넓이를 구한다고 생각하고 제곱을 하면 9가 되죠. 세 번째 사각형의 가로의 점은 5개가 있습니다. 넓이를 구한다고 생각하고 제곱을 하면 25가 되죠. 가로의 점은 현재 점 사이사이에 점이 추가되기 때문에 현재 점 - 1만큼 추가됩니다. 즉, 현재 가로의 점이 cnt라면 다음 가로의 점은 2..

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 풀이 자신을 제외한 약수를 반복문으로 구한 뒤 더해서 완전수이면 약수들의 합으로 나타내어 출력합니다. 완전수인지 판별, 출력 이렇게 반복문 두 번 돌려주시면 됩니다. 코드