멀쩡한 사각형
문제 링크 : 멀쩡한 사각형
문제 설명
가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다. 새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다.
가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요.
제한 사항
- W, H : 1억 이하의 자연수
입출력 예
| W | H | result |
|---|---|---|
| 8 | 12 | 80 |
풀이 방법
- W, H 값을 이용하여 쓸 수 없는 격자의 개수를 찾는 것이 문제의 핵심으로 보인다. 먼저 W, H가 최대공약수가 1 이상인 경우에는 최대공약수만큼의 패턴을 반복한다. W, H를 먼저 최대공약수로 나눠서 서로소로 만든 상태에서 몇 개의 칸이 대각선에 겹치는 지 확인해보았다.
- 대각선이 격자의 변에 닿는 개수가 영향을 끼치는 칸이니까, (W-1),(H-1)만큼의 칸에 닿고 처음 시작하는 칸까지 영향을 끼치니까 결과적으로 W + H - 1만큼의 격자칸은 못 쓰는 것으로 보인다. 그리고 처음에 최대공약수로 나눠줬기 때문에 최대공약수만큼 곱해준 칸만큼을 전체 칸에서 빼면 될 것으로 보인다.
-> 최대공약수를 구하는 알고리즘은O(logN)만큼의 시간복잡도가 걸리고, 다른 계산은O(1)만큼의 시간복잡도가 걸릴 것으로 보이기 때문에 알맞은 알고리즘으로 보인다. 정답이 long long이기 때문에 중간에 int 범위 오버를 조심해야 한다.
구현
#include <iostream>
using namespace std;
int gcd(int a, int b){
if(a < b) swap(a, b);
if(b == 0) return a;
return gcd(b, a % b);
}
long long solution(int w,int h) {
long long answer = (long long)w * h;
int gcd_Value = gcd(w, h);
answer -= ((w + h) / gcd_Value - 1) * gcd_Value;
return answer;
}시소 짝꿍
문제 링크 : 시소 짝꿍
문제 설명
어느 공원 놀이터에는 시소가 하나 설치되어 있습니다. 이 시소는 중심으로부터 2(m), 3(m), 4(m) 거리의 지점에 좌석이 하나씩 있습니다.
이 시소를 두 명이 마주 보고 탄다고 할 때, 시소가 평형인 상태에서 각각에 의해 시소에 걸리는 토크의 크기가 서로 상쇄되어 완전한 균형을 이룰 수 있다면 그 두 사람을 시소 짝꿍이라고 합니다. 즉, 탑승한 사람의 무게와 시소 축과 좌석 간의 거리의 곱이 양쪽 다 같다면 시소 짝꿍이라고 할 수 있습니다.
사람들의 몸무게 목록 weights이 주어질 때, 시소 짝꿍이 몇 쌍 존재하는지 구하여 return 하도록 solution 함수를 완성해주세요.
제한 사항
- 2 ≤ weights의 길이 ≤ 100,000
- 100 ≤ weights[i] ≤ 1,000
-> 몸무게 단위는 N(뉴턴)으로 주어집니다.
-> 몸무게는 모두 정수입니다.
입출력 예
| weights | result |
|---|---|
| [100,180,360,100,270] | 4 |
풀이 방법
- weights의 길이가 최대 100,000이기 때문에
O(N^2)의 알고리즘은 사용하면 안 되는 것을 생각해서, 이중 for문을 통해 검사를 한다면 시간 초과가 날 것으로 보인다. - weights[i] 범위는 100에서 1,000이기 때문에 unordered_map을 활용하여 weights의 개수를 세고, weights의 개수를 이중 for문을 통해 검사하면 최대 1,000의 개수이기 때문에 시간복잡도에서 괜찮지 않을까라는 생각을 가졌다.
- 먼저 무게가 같은 경우에는 n개 중에서 2개를 선택하는 방법의 개수를 통해 answer에 더하고, 배수 차이의 경우에는 먼저 정렬을 해서 이를 배수 비교해서 알맞다면 answer에 더하는 방법을 통해 정답을 구했다. 또한 답이 long long이기 때문에 중간에 int 범위 초과가 나는 것을 주의해야 한다.
-> 시간복잡도는 처음에 weights를 순회하는O(N)의 시간복잡도와 몸무게 목록들을 이중 for문을 돌기 때문에 최대O(N + K^2)의 시간복잡도가 걸릴 것으로 추정된다. N은 최대 100,000이고, K은 최대 1,000이기 때문에 알맞은 알고리즘으로 보인다.
구현
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
long long solution(vector<int> weights) {
long long answer = 0;
vector<int> weight;
unordered_map<int, int> weights_count;
for(int i : weights){
weights_count[i]++;
}
for(auto it = weights_count.begin(); it != weights_count.end(); it++){
weight.push_back(it->first);
// 무게가 같은 경우
if(it->second > 1){
answer += (long long)it->second * (it->second - 1) / 2;
}
}
sort(weight.begin(), weight.end());
for(int i = 0; i < weight.size() - 1; i++){
for(int j = i + 1; j < weight.size(); j++){
if((weight[i] * 3 == weight[j] * 2)
|| (weight[i] * 4 == weight[j] * 3)
|| (weight[i] * 2 == weight[j])){
answer += (long long)weights_count[weight[i]] * weights_count[weight[j]];
continue;
}
}
}
return answer;
}
게임 개발자를 향해..