[스터디] 문제 풀이 - 3주차

실 - 19592, 1590, 2121, 17124
골 - 23978, 2022
프 - 멀쩡한 사각형

---

19592번

문제

파이썬 풀이

t = int(input())

for _ in range(t):
    n, x, y = map(int, input().split())
    v = list(map(int, input().split()))
    
    max_val = max(v)
    my_val = v[-1]
    
    if max_val == my_val:
        print(0)
    elif y <= max_val:
        print(-1)
    else:
        target = x - (x / max_val - 1) * my_val
        if int(target) + 1 > y:
            print(-1)
        else:
            print(int(target) + 1)

이진탐색하기 싫어서 그냥 계산했다.

C++ 풀이

1590번

문제

파이썬 풀이

n, t = map(int, input().split())

time = []

INF = 99999999

for _ in range(n):
    s, i, c = map(int, input().split())
    
    c -= 1
    start = s
    end = s + i * c
    
    if s == t:
        time.append(0)
    elif end < t:
        time.append(INF)
    elif s > t:
        time.append(s - t)
    else:
        while start <= end:
            if c == 0:
                mid = start + i
            else:
                mid = s + i * (c // 2)
                c //= 2
            if mid >= t and mid < t + i:
                time.append(mid - t)
                break
            elif t < mid:
                end = mid
            else:
                start = mid

print(-1 if min(time) == INF else min(time))

풀긴했는데 내가 뭘 한건지..

C++ 풀이

2121번

문제

파이썬 오답 - 시간초과

n = int(input())
a, b = map(int, input().split())
dots = [list(map(int, input().split())) for _ in range(n)]

answer = 0

for x, y in dots:
    # 시간초과
    if [x+a, y] in dots and [x, y+b] in dots and [x+a, y+b] in dots:
        answer += 1

print(answer)

해당하는 점이 있는지 찾는 부분을 구현해야 하는 문제!
근데 귀찮으니까 일단 입력 방법 변화부터..

파이썬 풀이

import sys

input = sys.stdin.readline

n = int(input())
a, b = map(int, input().split())
dots = [tuple(map(int, input().split())) for _ in range(n)]
dots = set(dots)

answer = 0

for x, y in dots:
    if (x+a, y) in dots and (x, y+b) in dots and (x+a, y+b) in dots:
        answer += 1

print(answer)

이건 통과된다 input()이게 느려서 시간초과인 것 같다.

C++ 풀이

17124번

문제

파이썬 풀이

C++ 풀이

---

23978번

문제

파이썬 오답 - 시간초과

import sys
input = sys.stdin.readline

def coinToCash(coin):
    cash = coin * (coin + 1) // 2
    for i in range(n-1):
        diff = days[i+1] - days[i]
        if diff >= coin:
            cash += coin * (coin + 1) // 2
        else:
            cash += coin * diff - diff * (diff - 1) // 2
    return cash

n, k = map(int, input().split())
days = list(map(int, input().split()))

start = 0
end = k // n + 1

while start + 1 < end:
    mid = (start + end) // 2
    print(mid)
    if coinToCash(mid) >= k:
        end = mid
    else:
        start = mid

print(end)

아무래도 현금화 했을 때의 가격을 계산하는 함수를 수정해야할 것 같은데 어떻게 고쳐야 하는건지..

C++ 풀이

2022번

문제

파이썬 풀이

import sys
import math

input = sys.stdin.readline
def cal_c(d):
    h1 = math.sqrt(x*x - d*d)
    h2 = math.sqrt(y*y - d*d)
    c = h1 * h2 / (h1 + h2)
    return c  
    
x, y, c = map(float, input().split())
start = 0
end = min(x, y)
while abs(start - end) > 1e-6:
    mid = (start + end) / 2.0
    c2 = cal_c(mid)
    if c2 > c:
        start = mid
    else:
        end = mid
        
print(round(mid, 3))

C++ 풀이

---

멀쩡한 사각형

문제

W + H - 최대공약수 만큼의 사각형이 대각선에 의해 잘림

파이썬 풀이

from math import gcd

def solution(w,h):
    answer = w * h - (w + h - gcd(w, h))
    return answer

구현보다는 규칙을 발견하는게 어려웠던 문제였다.
최대공약수까지는 접근했는데 그 다음을 한참 생각했다.

C++ 풀이

using namespace std;

int gcd(int a, int b) {
    if(a >= b) return (a % b == 0 ? b : gcd(b, a % b));
    else return (b % a == 0 ? a : gcd(a, b % a));
}

long long solution(int w,int h) {
    long long answer;
    answer = (long long)w * h - (w + h - gcd(w, h));
    return answer;
}

w와 h의 곱이 int의 범위를 벗어난다는 것을 고려해야한다.
w와 h가 int 형식이라 둘을 곱할 때 long long으로 처리할 수 있도록 해야한다.
처음에는 이를 고려하지 않고 풀었다가 테스트 12~17을 계속 틀렸다.
또한 최대공약수를 구하기 위한 함수를 만들어야하는데,
이는 유클리드 호제법을 이용한다.