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

문제

음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다.

입력

출력

풀이방법

조합(Combination)을 이용해 문제를 해결하였다.

1 자릿수 >> 10 Combination 1 => 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 

2 자릿수 >> 10 Combination 2 => (0,1), (0,2), (0,3) ... (8,9)

* 여기서 tuple을 뒤집어서 합친다면 (10, 20, 30, ... 98 ) 이러한 방식으로 나온다. 

이러한 방식으로 10 Combination 1 to 10 까지 배열에 추가한 뒤, 배열을 정렬하면 감소하는 수의 배열이 된다.

배열의 길이 < N + 1 인 경우 : -1 출력, 그 외의 경우 배열[N]을 출력한다.

코드

from itertools import combinations

ans = []
comb = list(range(10))

for i in range(1,11):
    for j in combinations(comb,i):
        ans.append(int(''.join(list(map(str,reversed((j)))))))

ans.sort()

n = int(input())

if len(ans) < n+1:
    print(-1)
else:
    print(ans[n])

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

문제

왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다. 

아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.

아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.

입력

출력

풀이방법

9명의 난쟁이 중에서 2명의 난쟁이 키를 제외하는 방법을 BruteForce 방법을 이용해 계산하여 오름차순으로 출력한다.

코드

#include<bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;

typedef long long int ll;

int main()
{
  fastio;
  int K[9],sum_temp=0,i,j;
  for(int i=0;i<9;i++)
  {
    cin>>K[i];
    sum_temp+=K[i];
  }
  sort(K,K+9);
  const int sum=sum_temp;
  for(i=0;i<8;i++)
  {
    int B=0;
    for(j=i+1;j<9;j++)
    {
      if(sum-(K[i]+K[j])==100)
      {
        B=1; 
        break;
      }
    }
    if(B) break;
  }
  for(int l=0;l<9;l++)
  {
    if(i==l or j==l) continue;
    else cout<<K[l]<<"\n";
  }
}

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

문제

창영이는 이번학기에 어떤 교양수업을 듣고 있다. 그런데, 그 교수님은 매우 지각을 자주 하시고 게다가 수업에 지각을 하였을 경우 수업을 일찍 마쳐 주기까지 하는 것을 발견하였다.

창영이는 교수님의 지각시간 0이상의 정수 t와 수업을 일찍 마쳐주는 시간 s 사이에 다음과 같은 관계가 있음을 알았다.

$s = t^2$

문득 창영이는 수업시간 d가 주어졌을 때, 교수님이 얼마나 지각을 할 수 있는지 궁금해졌고, 여러분은 창영이를 도와서 교수님이 지각할 수 있는 최대의 시간을 알아보자. 물론, 교수님이 도착하자마자 수업을 일찍 마쳐서 수업이 끝나는 것도 가능하다. 예를 들어, 수업시간이 6분인 경우, 교수님이 2분 지각을 하면, 4분간 수업을 일찍 마치게 되고, 2+4=6이기 때문에 바로 수업을 끝낼 수 있다. 또 다른 예로, 수업시간이 7분인 경우 교수님이 2분 지각을 하면, 수업을 4분 일찍 마쳐줄 수 있고, 2+4≤7 이므로 가능한 경우가 되고, 교수님이 3분 지각을 하게 되면, 수업을 9분 일찍 마쳐야 되고, 3+9>7 이므로, 교수님이 3분 지각을 하는 것은 불가능하다. 따라서, 교수님은 수업시간이 7분인 경우 교수님은 최대 2분간 지각을 할 수 있다.

입력

출력

풀이방법

$t$의 제곱근을 구하고 현재 시간에 지각이 가능한지 구한다.($ t + t^2 <= s$)

만약 불가능하다면 $t$를 1 빼고 계산한다.

while문 탈출할 때의 $t$ 값이 정답이다.

코드

import sys
input = sys.stdin.readline

def main():
    n = int(input())
    for _ in range(n):
        s = int(input())
        t = int(s**0.5)
        while (t + t**2) > s:
            t -= 1
        print(t)
if __name__ =='__main__':
    main()

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

문제

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력

출력

풀이방법

위와 같은 방식으로  일반식을 도출해낼 수 있다.

초기 값은 이러하다. $f(1) = 1 $, $f(2) = 3$ 

$f(3)$ 부터는 빨간색과 회색을 통해서 일반식을 구할 수 있다. 

$f(n) = f(n-1) + 2f(n-2)$ 와 같은 일반식으로 도출할 수 있다.

마지막으로 구한 값에 10007로 나누어 값을 할당한다.

코드

import sys

input = sys.stdin.readline

dp = [0 for _ in range(1001)]

dp[1] = 1
dp[2] = 3

N = int(input())

for i in range(3, N+1):
    dp[i] = (dp[i-1] +2 * dp[i-2]) % 10007

print(dp[N])

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

문제

춘향이는 편의점 카운터에서 일한다.

손님이 2원짜리와 5원짜리로만 거스름돈을 달라고 한다. 2원짜리 동전과 5원짜리 동전은 무한정 많이 가지고 있다. 동전의 개수가 최소가 되도록 거슬러 주어야 한다. 거스름돈이 n인 경우, 최소 동전의 개수가 몇 개인지 알려주는 프로그램을 작성하시오.

예를 들어, 거스름돈이 15원이면 5원짜리 3개를, 거스름돈이 14원이면 5원짜리 2개와 2원짜리 2개로 총 4개를, 거스름돈이 13원이면 5원짜리 1개와 2원짜리 4개로 총 5개를 주어야 동전의 개수가 최소가 된다.

입력

출력

풀이방법

1. 5원 코인 수, 2원 코인 수와 제외한 나머지 값을 구한다. (a, b, m)

2. 나머지 값(m)이 0이면 a와 b의 값을 더해서 출력한다.

3. 나머지 값이 0이 아니라면

  ㄱ. 5원 코인 수에서 1을 뺍니다.

  ㄴ. 나머지 값 5를 더합니다.

  ㄷ. 나머지 값을 통해 2원 코인의 수를 더합니다.

  ㄹ. 나머지 값에 2로 나눈 나머지 값으로 바꿉니다.

  ㅁ. 2번으로 돌아갑니다.

코드

# 빠른 입출력
import sys
input = sys.stdin.readline

n = int(input())
if n == 1 or n == 3:
    print(-1)
    exit(0)


a = n // 5
b = (n - a * 5) // 2
m = n - (a * 5 + b * 2)

while m != 0:
    a -= 1
    m += 5
    b += m // 2
    m = m % 2

print(a+b)

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

문제

어린시절 다들 한 번씩은 이름으로 궁합을 본 적이 있을 것이다. 이것과 비슷한 방식으로 중앙대학교에는 핸드폰 번호 궁합을 보는 것이 유행이라고 한다.

핸드폰 번호 궁합을 보기 위해서는 먼저 궁합을 보고싶은 두 중앙대생 A와 B의 핸드폰 번호에서 맨 앞의 010과 "-"(하이픈)을 모두 제외한 후, A부터 시작하여 한 숫자씩 번갈아가면서 적는다. 그리고 인접한 두 숫자끼리 더한 값의 일의 자리를 두 숫자의 아래에 적어나가면서 마지막에 남는 숫자 2개로 궁합률을 구하게 된다.

예를 들어, 아래의 그림과 같이 A의 번호가 010-7475-9336 이고, B의 번호가 010-3619-5974 이면, 7346715995393764에서 시작하여 070386484822030, 77314022204233, 4045424424656, 449966866011, 83852442612, 1137686873, 240344450, 64378895, 0705674, 775131, 42644, 6808, 488, 26이 되어 둘은 26%의 궁합률을 가지게 된다.

위의 예시에서처럼 인접한 두 숫자를 더한 값이 두자리 정수가 되더라도, 일의 자리 숫자만 적는다. 가령 7과 3을 더하면 0을 적고, 4와 8을 더하면 2를 적는다.

중앙대학교에서 유행인 핸드폰 번호 궁합률을 알아보는 프로그램을 작성해보자. 단, A와 B의 핸드폰 번호는 다르다고 가정한다.

입력

출력

풀이방법

DP 방식으로 접근해서 해결했습니다.

1. 번호를 list에 번갈아가면서 저장합니다.

2. 2개의 번호를 계산한 값을 10으로 나눈 몫을 list에 저장합니다. 리스트의 마지막까지 계산하면 마지막 원소를 제거합니다.

3. list의 길이가 2가 되면 while문을 정지하고 값을 출력합니다.

코드

import sys
input = sys.stdin.readline

a = input().rstrip()
b = input().rstrip()
ans = []

for i in range(len(a)):
    ans.append(int(a[i]))
    ans.append(int(b[i]))

while len(ans) > 2:
    for i in range(len(ans)-1):
        ans[i] = (ans[i] + ans[i+1]) % 10
    ans.pop()
print(''.join(map(str,ans)))

결론

브론즈 1 문제여서 그런지 정말 간단한 문제였다.