poorman

https://www.acmicpc.net/problem/1712

문제

월드전자는 노트북을 제조하고 판매하는 회사이다. 노트북 판매 대수에 상관없이 매년 임대료, 재산세, 보험료, 급여 등 A만원의 고정 비용이 들며, 한 대의 노트북을 생산하는 데에는 재료비와 인건비 등 총 B만원의 가변 비용이 든다고 한다.

예를 들어 A=1,000, B=70이라고 하자. 이 경우 노트북을 한 대 생산하는 데는 총 1,070만원이 들며, 열 대 생산하는 데는 총 1,700만원이 든다.

노트북 가격이 C만원으로 책정되었다고 한다. 일반적으로 생산 대수를 늘려 가다 보면 어느 순간 총 수입(판매비용)이 총 비용(=고정비용+가변비용)보다 많아지게 된다. 최초로 총 수입이 총 비용보다 많아져 이익이 발생하는 지점을 손익분기점(BREAK-EVEN POINT)이라고 한다.

A, B, C가 주어졌을 때, 손익분기점을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 21억 이하의 자연수이다.

출력

첫 번째 줄에 손익분기점 즉 최초로 이익이 발생하는 판매량을 출력한다. 손익분기점이 존재하지 않으면 -1을 출력한다.

해결 방안

1. 손익분기점을 구하기 위한 판매개수를 n으로 두고 수학적으로 접근한다.

생산비용 = A + (B * n) 
판매비용 = C * n 
손익 분기점 = (판매비용 - 생산비용 > 0) 
= (C*n) - (A + (B*n)) > 0 
= (C-B)*n - A > 0 
= n > A / (C-B) 

2. 손익 = (C-B)*n - A 에서 A,B,C는 자연수이므로 C-B가 0보다 작거나 같으면 손익은 항상 음수이므로 손익 분기점이 존재하지
않는다.(n = -1)
3. n > A / (C-B) 를 만족하는 n은 math.floor(A/(C-B) + 1)을 이용하여 구할 수 있다. 이는 다음과 같은
코드와 같은 작업을 한다.

if (A % (C-B) == 0): 
n = A//(C-B) + 1 
else: 
n = A//(C-B) + 2 

4. 2,3을 코드로 정리하면 다음과 같다.

if C - B <= 0: 
  n = -1 
else: 
  n = math.floor(A/(C-B) + 1) 

소스 코드

import sys, math 
input = sys.stdin.readline 

''' 
cost = A + (B * n) 
sale = C * n 
BreakEventPoint = (sale - cost > 0) 
sale - cost > 0 
 = (C*n) - (A + (B*n)) > 0 
 = (C-B)*n - A > 0 
 = n > A / (C-B) 

if C - B <= 0: 
  n = -1 
else: 
  n = math.floor(A/(C-B) + 1) 

''' 
def BreakEventPoint(A,B,C): 
  if C - B <= 0: 
    n = -1 
  else: 
    n = math.floor(A/(C-B) + 1) 
  return n 

def main(): 
  # input 
  A,B,C = list(map(float, input().split())) 
  n = BreakEventPoint(A,B,C) 
  print(n) 

main() 

https://www.acmicpc.net/problem/2588

문제

(세 자리 수) × (세 자리 수)는 다음과 같은 과정을 통하여 이루어진다.

(1)과 (2)위치에 들어갈 세 자리 자연수가 주어질 때 (3), (4), (5), (6)위치에 들어갈 값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 (1)의 위치에 들어갈 세 자리 자연수가, 둘째 줄에 (2)의 위치에 들어갈 세자리 자연수가 주어진다.

출력

첫째 줄부터 넷째 줄까지 차례대로 (3), (4), (5), (6)에 들어갈 값을 출력한다.

해결 방안

1. 두 자연수를 X, Y로 문자 입력을 받아서 Y의 뒷자리 수부터 차례대로 X와 곱한 값을 (3),(4),(5)를 구한 후 더하여 (6)을 구한다.

2. (3) = int(X) * int(Y[2])

3. (4) = int(X) * int(Y[1])

4. (5) = int(X) * int(Y[0])

5. (6) = (3) + (4)*10 + (5)*100

소스 코드

import sys
input = sys.stdin.readline
X = input().strip()
Y = input().strip()

v3 = int(X) * int(Y[2])
v4 = int(X) * int(Y[1])
v5 = int(X) * int(Y[0])
v6 = v3 + v4*10 + v5*100
print(v3)
print(v4)
print(v5)
print(v6)

https://www.acmicpc.net/problem/10818

문제

N개의 정수가 주어진다. 이때, 최솟값과 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 N개의 정수를 공백으로 구분해서 주어진다. 모든 정수는 -1,000,000보다 크거나 같고, 1,000,000보다 작거나 같은 정수이다.

출력

첫째 줄에 주어진 정수 N개의 최솟값과 최댓값을 공백으로 구분해 출력한다.

해결방안

1. 둘째 줄의 N개의 정수를 하나의 리스트로 만든다,

2. min(list) 내부모듈 함수를 이용하여 최솟값을 구한다.

3. max(list) 내부모듈 함수를 이용하여 최댓값을 구한다.

소스 코드

import sys
input = sys.stdin.readline
N = int(input())
numbers = list(map(int, input().split()))
min_n = min(numbers)
max_n = max(numbers)
print(' '.join(list(map(str, [min_n, max_n]))))

https://www.acmicpc.net/problem/2562

문제

9개의 서로 다른 자연수가 주어질 때, 이들 중 최댓값을 찾고 그 최댓값이 몇 번째 수인지를 구하는 프로그램을 작성하시오.

예를 들어, 서로 다른 9개의 자연수

3, 29, 38, 12, 57, 74, 40, 85, 61

이 주어지면, 이들 중 최댓값은 85이고, 이 값은 8번째 수이다.

입력

첫 째 줄부터 아홉 번째 줄까지 한 줄에 하나의 자연수가 주어진다. 주어지는 자연수는 100 보다 작다.

출력

첫째 줄에 최댓값을 출력하고, 둘째 줄에 최댓값이 몇 번째 수인지를 출력한다.

해결방안

1. 첫 째 줄부터 아홉 번째 줄까지의 자연수를 리스트에 차례대로 추가(append)한다.

2. 최대값은 max(list) 함수를 이용하여 구한다.

3. 최대값의 인덱스 값은 list.index(max_value)+1 로 구한다.

소스코드

import sys

numbers = []
for line in sys.stdin:
    numbers.append(int(line.strip()))
max_n = max(numbers)
max_idx = numbers.index(max_n)
print(max_n)
print(max_idx+1)

https://www.acmicpc.net/problem/2884

문제

상근이는 매일 아침 알람을 듣고 일어난다. 알람을 듣고 바로 일어나면 다행이겠지만, 항상 조금만 더 자려는 마음 때문에 매일 학교를 지각하고 있다.

상근이는 모든 방법을 동원해보았지만, 조금만 더 자려는 마음은 그 어떤 것도 없앨 수가 없었다.

이런 상근이를 불쌍하게 보던, 창영이는 자신이 사용하는 방법을 추천해 주었다.

바로 "45분 일찍 알람 맞추기"이다.

이 방법은 단순하다. 원래 맞춰져있는 알람을 45분 앞서는 시간으로 바꾸는 것이다. 어차피 알람 소리를 들으면, 알람을 끄고 조금 더 잘 것이기 때문이다. 이 방법을 사용하면, 매일 아침 더 잤다는 기분을 느낄 수 있고, 학교도 지각하지 않게 된다.

현재 상근이가 맞춰논 알람 시각이 주어졌을 때, 창영이의 방법을 사용한다면, 이를 언제로 고쳐야 하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 H와 M이 주어진다. (0 ≤ H ≤ 23, 0 ≤ M ≤ 59) 그리고 이것은 현재 상근이가 맞춰놓은 알람 시간 H시 M분을 의미한다.

입력 시간은 24시간 표현을 사용한다. 24시간 표현에서 하루의 시작은 0:0(자정)이고, 끝은 23:59(다음날 자정 1분 전)이다. 시간을 나타낼 때, 불필요한 0은 사용하지 않는다.

출력

첫째 줄에 상근이가 창영이의 방법을 사용할 때, 맞춰야 하는 알람 시간을 출력한다. (입력과 같은 형태로 출력하면 된다.)

해결 방안

1. H시 M분에서 45분을 뺀 값을 H'시 M'분이라고 했을 때, 두가지 케이스로 나눠서 생각해볼 수 있다.

1-1. M >= 45 인 경우에는 M-45 >= 0 이므로

  H' = H, M' = M -45

1-2. M < 45 인 경우에는 M-45 < 0 이므로

  H' = H-1, M' = M - 45 + 60 (여기서 H가 0 인 경우에는 H = 23이 된다)

2. 1.번의 케이스를 모드(%)를 이용하면 간단하게 값을 표시할 수 있다.

  M' = (M -45 + 60) % 60 (M < 45인 경우에는  H' = (H + 24 - 1) % 24)

소스 코드

import sys
input = sys.stdin.readline

def TimeAlarm(H, M):
    h = 24
    m = 60
    alarm = 45
    
    if M < alarm:
        H = (H + h - 1) % h
    M = (M + m - alarm) % m
    return H, M
    
H, M = list(map(int, input().split()))
H2, M2 = TimeAlarm(H, M)
print(' '.join(list(map(str,[H2,M2]))))

https://www.acmicpc.net/problem/10871

문제

정수 N개로 이루어진 수열 A와 정수 X가 주어진다. 이때, A에서 X보다 작은 수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 X가 주어진다. (1 ≤ N, X ≤ 10,000)

둘째 줄에 수열 A를 이루는 정수 N개가 주어진다. 주어지는 정수는 모두 1보다 크거나 같고, 10,000보다 작거나 같은 정수이다.

출력

X보다 작은 수를 입력받은 순서대로 공백으로 구분해 출력한다. X보다 작은 수는 적어도 하나 존재한다.

해결 방안

1. filter 함수를 이용하여 X보다 작은 수만 필터링한다.

소스 코드

import sys
input = sys.stdin.readline

N,X = map(int, input().split())
A = map(int, input().split())
s = map(str, list(filter(lambda x: x < X, A)))
print(' '.join(s))

https://www.acmicpc.net/problem/15552

문제

본격적으로 for문 문제를 풀기 전에 주의해야 할 점이 있다. 입출력 방식이 느리면 여러 줄을 입력받거나 출력할 때 시간초과가 날 수 있다는 점이다.

C++을 사용하고 있고 cin/cout을 사용하고자 한다면, cin.tie(NULL)과 sync_with_stdio(false)를 둘 다 적용해 주고, endl 대신 개행문자(\n)를 쓰자. 단, 이렇게 하면 더 이상 scanf/printf/puts/getchar/putchar 등 C의 입출력 방식을 사용하면 안 된다.

Java를 사용하고 있다면, Scanner와 System.out.println 대신 BufferedReader와 BufferedWriter를 사용할 수 있다. BufferedWriter.flush는 맨 마지막에 한 번만 하면 된다.

Python을 사용하고 있다면, input 대신 sys.stdin.readline을 사용할 수 있다. 단, 이때는 맨 끝의 개행문자까지 같이 입력받기 때문에 문자열을 저장하고 싶을 경우 .rstrip()을 추가로 해 주는 것이 좋다.

또한 입력과 출력 스트림은 별개이므로, 테스트케이스를 전부 입력받아서 저장한 뒤 전부 출력할 필요는 없다. 테스트케이스를 하나 받은 뒤 하나 출력해도 된다.

자세한 설명 및 다른 언어의 경우는 이 글에 설명되어 있다.

이 블로그 글에서 BOJ의 기타 여러 가지 팁을 볼 수 있다.

입력

첫 줄에 테스트케이스의 개수 T가 주어진다. T는 최대 1,000,000이다. 다음 T줄에는 각각 두 정수 A와 B가 주어진다. A와 B는 1 이상, 1,000 이하이다.

출력

각 테스트케이스마다 A+B를 한 줄에 하나씩 순서대로 출력한다.

해결 방안

1. sys.stdin.readline()을 이용하여 input()보다 빠른 입력을 받아 처리한다.

언어별 빠른 입출력 방법 : https://www.acmicpc.net/board/view/22716

BOJ 팁 : https://www.acmicpc.net/blog/view/55

소스 코드

import sys
input = sys.stdin.readline
N = int(input())
for n in range(N):
    x,y = map(int, input().split())
    print(x+y)

https://www.acmicpc.net/problem/1850

문제

모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오.

예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A가 111이고, B가 111111인 경우에는 최대공약수가 111이다.

입력

첫째 줄에 두 자연수 A와 B를 이루는 1의 개수가 주어진다. 입력되는 수는 2^63보다 작은 자연수이다.

출력

첫째 줄에 A와 B의 최대공약수를 출력한다. 정답은 천만 자리를 넘지 않는다.

해결방안

1. 같은 숫자로 이루어진 두 수의 최대공약수는 유클리드 호제법을 이용하여 자릿수 연산으로 구할 수 있다.

111/111/11 % 111 = 11
       (8) % (3) = (2)

소스코드

# Greatest Common Divisor
def GCD(x,y):
    x,y = max(x,y), min(x,y)
    while(y > 0):
        z = x % y
        if z == 0:
            return y
        x,y = y,z
    return x

x,y = map(int, input().split())
print('1'*GCD(x,y))

https://www.acmicpc.net/problem/2839

문제

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.

상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.

상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)

출력

상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.

해결 방안

1. 봉지의 수를 최소화 하기 위해서는 최대한 5킬로그램 봉지를 많이 사용하면 된다.

2. N을 5로 나눈 최대치에서 1씩 줄여가면서 남은 N값이 3으로 나누어 떨어지는 순간에 봉지 개수를 리턴한다.

3. 5와 3으로 나누어 떨어지지 않는 경우에 -1을 리턴한다.

소스 코드

N = int(input())

def count_bag(x):
    bag1 = 5
    bag2 = 3
    max_bag1 = x//5
    for i in range(max_bag1+1):
        cnt1 = max_bag1 - i
        rest_x = x-(cnt1*bag1)
        if rest_x % bag2 != 0:
            continue
        cnt2 = rest_x // bag2
        return cnt1 + cnt2
    return -1

print(count_bag(N))

https://www.acmicpc.net/problem/10826

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 10,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 n번째 피보나치 수를 출력한다.

해결 방안 - 1

1. 재귀 함수를 이용한다. f(n+2) = f(n+1) + f(n)

2-1. 함수 f(n)는 n이 0일때 0, 1일때 1을 리턴한다.

2-2. n이 2이상의 경우에 f(n-2) + f(n-1)을 리턴한다.

소스코드 - 1

n = int(input())

def fibonacci(x):
    if x == 0:    return 0
    if x == 1:    return 1
    return fibonacci(x-1) + fibonacci(x-2)
    
print("%d" % fibonacci(n))

*재귀 함수를 사용하는 경우에 x가 커질수록 메모리 사용량과 연산 시간이 증가하여 시간 초과로 실패한다.

해결 방안 - 2

1. Dynamic Programming 알고리즘으로 n-1, n-2번째의 수만 메모리에 갱신하여 연산해 나간다.

2. 파이썬의 특징을 활용하여 x, y = y, x+y 연산으로 x에는 n-1번째 값을, y에는 n-1번째와 n-2번째의 합을 취한다.

소스코드 - 2

n = int(input())

def fibonacci(k):
    x, y = 0, 1
    for i in range(k):
        x, y = y, x+y
    return x 

print("%d" % fibonacci(n))