poorman

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

문제

서울시는 6월 1일부터 교통 혼잡을 막기 위해서 자동차 10부제를 시행한다. 자동차 10부제는 자동차 번호의 일의 자리 숫자와 날짜의 일의 자리 숫자가 일치하면 해당 자동차의 운행을 금지하는 것이다. 예를 들어, 자동차 번호의 일의 자리 숫자가 7이면 7일, 17일, 27일에 운행하지 못한다. 또한, 자동차 번호의 일의 자리 숫자가 0이면 10일, 20일, 30일에 운행하지 못한다.

여러분들은 일일 경찰관이 되어 10부제를 위반하는 자동차의 대수를 세는 봉사활동을 하려고 한다. 날짜의 일의 자리 숫자가 주어지고 5대의 자동차 번호의 일의 자리 숫자가 주어졌을 때 위반하는 자동차의 대수를 출력하면 된다.

입력

첫 줄에는 날짜의 일의 자리 숫자가 주어지고 두 번째 줄에는 5대의 자동차 번호의 일의 자리 숫자가 주어진다. 날짜와 자동차의 일의 자리 숫자는 모두 0에서 9까지의 정수 중 하나이다. 

출력

주어진 날짜와 자동차의 일의 자리 숫자를 보고 10부제를 위반하는 차량의 대수를 출력한다.

소스코드 - 파이썬

import sys
input = sys.stdin.readline

d = int(input())
cars = map(int, input().split())
answer = 0
for c in cars:
    if c == d:
        answer += 1
print(answer)

소스코드 - C++

#include <cstdio>
using namespace std; 

int main(int argc, char** argv) 
{
    int d, car, i;
    int cnt = 0;
    scanf("%d", &d);
    
    for(i=0; i<5; i++) {
        scanf("%d", &car);
        if (d == car) {
            cnt++;
        }
    }
    printf("%d", cnt);
}

소스코드 - Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int i, cnt = 0;
        for(i=0; i<5; i++) {
            if(n == sc.nextInt()) {
                cnt++;
            }
        }
        System.out.println(cnt);
    }
}

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

문제

예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요.

입력

첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다.

출력

첫째 줄부터 2×N-1번째 줄까지 차례대로 별을 출력한다.

해결방안

1. 각 K번째 줄에 대해 다음과 같은 출력을 정의한다.

2. 1 ~ N-1번째 줄에는 별을 (N-K)*2+1개 출력한다.

3. N번째 줄에는 별을 1개 출력한다.

4. N+1 ~ 2N-1번째 줄에는 별을 (K-N)*2+1개 출력한다.

2. 모든 출력은 2*N-1개의 길이를 갖은 문자열 중앙정렬로 출력한다.

소스코드 - 파이썬

import sys
input = sys.stdin.readline

# k : star, n : max_len
def midStar(k, n):
    blank = " "
    star = "*"
    stars = star * k
    blanks = blank * ((n-k)//2)
    return blanks + stars

def printStars(n):
    l = 2*n-1
    for k in range(1,l+1):
        if k == n:
            s = midStar(1, l)
        elif k < n:
            s = midStar((n-k)*2+1, l)
        elif k > n:
            s = midStar((k-n)*2+1, l)
        print(s)

N = int(input())
printStars(N)

소스코드 - C++

#include <cstdio>
#include <string>
#include <iostream>
using namespace std;

string midStar(int k, int n) {
    string blank = " ";
    string star = "*";
    string stars = "";
    int blank_n = (n-k)/2;
    int star_n = k;
    int i;
    for (i=0; i<blank_n; i++) {
        stars.append(blank);
    }
    for (i=0; i<star_n; i++) {
        stars.append(star);
    }
    return stars;
}

int main() {
    int n, k;
    string s;
    scanf("%d", &n);
    
    int l = 2*n-1;
    for(k=1; k<l+1; k++) {
        if (k == n) {
            s = midStar(1, l);
        } else if (k < n) {
            s = midStar((n-k)*2+1, l);
        } else if (k > n) {
            s = midStar((k-n)*2+1, l);
        }
        cout << s << endl;
    }
}

소스코드 - Java

import java.util.*;

public class Main {
    public static String midStar(int k, int n) {
        String blank = new String(" ");
        String star = new String("*");
        String stars = new String("");
        int blank_n = (n-k)/2;
        int star_n = k;
        int i;
        for (i=0; i<blank_n; i++) {
            stars += blank;
        }
        for (i=0; i<star_n; i++) {
            stars += star;
        }
        return stars;
    }    
    
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int l = 2*n-1;
        int k;
        String s = new String("");
        for (k=1; k<l+1; k++) {
            if (k == n) {
                s = midStar(1, l);
            } else if (k < n) {
                s = midStar((n-k)*2+1, l);
            } else if (k > n) {
                s = midStar((k-n)*2+1, l);
            }
            System.out.println(s);
        }
    }
}

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

문제

흔한 수학 문제 중 하나는 주어진 점이 어느 사분면에 속하는지 알아내는 것이다. 사분면은 아래 그림처럼 1부터 4까지 번호를 갖는다. "Quadrant n"은 "제n사분면"이라는 뜻이다.

예를 들어, 좌표가 (12, 5)인 점 A는 x좌표와 y좌표가 모두 양수이므로 제1사분면에 속한다. 점 B는 x좌표가 음수이고 y좌표가 양수이므로 제2사분면에 속한다.

점의 좌표를 입력받아 그 점이 어느 사분면에 속하는지 알아내는 프로그램을 작성하시오. 단, x좌표와 y좌표는 모두 양수나 음수라고 가정한다.

입력

첫 줄에는 정수 x가 주어진다. (−1000 ≤ x ≤ 1000; x ≠ 0) 다음 줄에는 정수 y가 주어진다. (−1000 ≤ y ≤ 1000; y ≠ 0)

출력

점 (x, y)의 사분면 번호(1, 2, 3, 4 중 하나)를 출력한다.

해결방안

1. (x > 0 and y > 0) : 1사분면

2. (x < 0 and y > 0) : 2사분면

3. (x < 0 and y < 0) : 3사분면

4. (x > 0 and y < 0) : 4사분면

소스코드 - 파이썬

import sys
input = sys.stdin.readline

def Quadrant(x,y):
    if x > 0:
        if y > 0:
            return 1
        elif y < 0:
            return 4
    elif x < 0:
        if y > 0:
            return 2
        elif y < 0:
            return 3
    return 0

x = int(input())
y = int(input())
q = Quadrant(x,y)
print(q)

소스코드 - C++

#include <cstdio>
using namespace std;

int Quadrant(int x, int y) {
    int q = 0;
    if (x > 0) {
        if (y > 0) {
            q = 1;
        } else if (y < 0) {
            q = 4;
        }
    } else if (x < 0) {
        if (y > 0) {
            q = 2;
        } else if (y < 0) {
            q = 3;
        }
    }
    return q;
}

int main() {
    int x, y, q;
    scanf("%d", &x);
    scanf("%d", &y);
    q = Quadrant(x, y);
    printf("%d", q);
}

소스코드 - Java

import java.util.*;

public class Main {
    public static int Quadrant(int x, int y){
        int q = 0;
        if (x > 0) {
            if (y > 0) {
                q = 1;
            } else if (y < 0) {
                q = 4;
            }
        } else if (x < 0) {
            if (y > 0) {
                q = 2;
            } else if (y < 0) {
                q = 3;
            }
        }
        return q;
    }

    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int y = sc.nextInt();
        int q = Quadrant(x,y);
            
        System.out.println(q);
    }
}

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/1463

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

해결 방안 - 1

1. 너비우선탐색(BFS) 알고리즘을 이용하여 N 값이 1이 될때까지 탐색한다.

2. FIFO 큐를 사용하기 위해서 collections.deque를 이용하여 popleft로 값을 꺼낸 후에 새로운 노드를 append한다.

3. 노드 값은 [value, count] 형태로 사용하고 너비 우선 탐색이므로 value가 1이 되는 순간의 count를 리턴한다.

소스 코드 - 1

import sys
from collections import deque
input = sys.stdin.readline

N = int(input())

def BFS(x):
    cnt = 0
    Q = deque([(x,cnt)])
    while(Q):
        x,cnt = Q.popleft()
        if x == 1:
            return cnt
        if x % 3 == 0:
            Q.append([x//3,cnt+1])
        if x % 2 == 0:
            Q.append([x//2,cnt+1])
        Q.append([x-1,cnt+1])
    return -1

print(BFS(N))

수행시간 : 2372ms

해결 방안 - 2

1. 깊이우선탐색(DFS) 알고리즘을 이용하여 N 값이 1이 될때까지 탐색한다.

2. LIFO 스택을 사용하여 pop으로 값을 꺼낸 후에 새로운 노드를 append한다.

3. 노드 값은 [value, count] 형태로 사용하고 value 값이 1이 되는 순간의 count값으로 min_count의 최소 값을 갱신한다.

4. 최소 count 값만 구하면 되기 때문에 min_count보다는 더 깊게 탐색하지 않는다.

5. 깊이 우선 탐색이 모두 끝났을 때 min_count값을 리턴한다.

소스 코드 - 2

import sys
from collections import deque
input = sys.stdin.readline

N = int(input())
def DFS(x):
    min_cnt = x
    cnt = 0
    Q = deque([(x,cnt)])
    while(Q):
        x,cnt = Q.pop()
        if cnt >= min_cnt:
            continue
        if x == 1:
            min_cnt = min(min_cnt, cnt)
        Q.append([x-1,cnt+1])
        if x % 2 == 0:
            Q.append([x//2,cnt+1])
        if x % 3 == 0:
            Q.append([x//3,cnt+1])
    return min_cnt

print(DFS(N))

수행시간 : 1272ms

* 해당 문제는 BFS/DFS의 탐색에 시간이 많이 소요되어 비효율적이다.

해결 방안 - 3

1. 재귀함수를 이용하여 현재 위치에 도달하는 최소 코스트를 리턴한다.

2. 현재 위치의 최소 코스트에 도달하기 위해서는 2,3으로 나누어 떨어지는 거리(x//2,x//3) + 나머지 거리(x%2,x%3) + 1이다. f(x) = min( f(x//3) + x%3 + 1, f(x//2) + x%2 + 1)

3. 거리가 1일때는 0, 거리가 2,3일때는 1의 코스트가 든다. f(1) = 0, f(2) = 1, f(3) = 1

소스 코드 - 3

import sys
input = sys.stdin.readline

N = int(input())
def fnc(x):
    if x == 1:
        return 0
    elif x <= 3:
        return 1
    return min(fnc(x//3) + x%3 + 1, fnc(x//2) + x%2 + 1)
print(DP(N))

수행시간 : 72ms

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

문제

0보다 크거나 같고, 99보다 작거나 같은 정수가 주어질 때 다음과 같은 연산을 할 수 있다. 먼저 주어진 수가 10보다 작다면 앞에 0을 붙여 두 자리 수로 만들고, 각 자리의 숫자를 더한다. 그 다음, 주어진 수의 가장 오른쪽 자리 수와 앞에서 구한 합의 가장 오른쪽 자리 수를 이어 붙이면 새로운 수를 만들 수 있다. 다음 예를 보자.

26부터 시작한다. 2+6 = 8이다. 새로운 수는 68이다. 6+8 = 14이다. 새로운 수는 84이다. 8+4 = 12이다. 새로운 수는 42이다. 4+2 = 6이다. 새로운 수는 26이다.

위의 예는 4번만에 원래 수로 돌아올 수 있다. 따라서 26의 사이클의 길이는 4이다.

N이 주어졌을 때, N의 사이클의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. N은 0보다 크거나 같고, 99보다 작거나 같은 정수이다.

출력

첫째 줄에 N의 사이클 길이를 출력한다.

해결 방안

1. N의 10의 자리 숫자는 N//10 (몫), 1의 자리 숫자는 N%10 (나머지)가 된다.

2. 새로운 수 s는 N의 나머지가 10의 자리 숫자(N%10*10)가 되고,

몫과 나머지를 더한 수의 1의 자리 숫자((N//10 + N%10)%10)가 1의 자리 숫자가 된다.

3. s값으로 1,2를 반복하여 새로운 s값이 N가 같아질 때까지 반복한다.

소스 코드

import sys
input = sys.stdin.readline

N = int(input())
s = N
cnt = 0
while(True):
    x = s//10
    y = s%10
    s = 10*y + ((x+y)%10)
    cnt += 1
    if s == N:
        break
print(cnt)