문제

수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장 났다.

리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고 있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대만큼 있다.

수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장 났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야 하는지 구하는 프로그램을 작성하시오.

수빈이가 지금 보고 있는 채널은 100번이다.

입력

출력

풀이방법

알고리즘은 생각보다 간단했다.

1. 만들 수 있는 수 중에서 목표와 가장 가까운 수를 찾는다.

2. 가장 가까운 수와 목표 번호와의 차이를 구한다.

가장 가까운 수를 찾는 방법 = 브루트포스를 사용하면 된다.

1부터 시작해서 1,000,000까지 숫자 중 만들 수 있는 수를 찾는다.

알고리즘 구현은 밑에 코드에 자세하게 적어놨다.

코드

# gold
# 리모컨
import sys

def main():
    target = int(input())
    # ++ or -- 로 이동할 경우 -> 최댓값
    ans = abs(100 - target)  
    
    # 고장난 버튼 입력
    M = int(input())
    if M > 0:
        broken = set(input().split())
    else:
        broken = set()

    # 작은수에서 큰수로 이동할 땐 500,000이며
    # 큰수에서 작은수로 이동할 땐 1,000,000까지 봐야한다.
    for num in range(1000001):
        for N in str(num):
        	# 만들 수 없는 숫자인 경우
            if N in broken: 
                break
        # 만들 수 있는 숫자인 경우  
        else:  
            # min(기존 답, 버튼을 누른 횟수 + 해당 번호와의 차이)
            if ans > len(str(num)) + abs(num - target):
                ans = len(str(num)) + abs(num - target)

    print(ans)


if __name__ == '__main__':
    input = sys.stdin.readline
    main()

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

문제

solved.ac는 Sogang ICPC Team 학회원들의 알고리즘 공부에 도움을 주고자 만든 서비스이다. 지금은 서강대뿐만 아니라 수많은 사람들이 solved.ac의 도움을 받아 알고리즘 공부를 하고 있다.

ICPC Team은 백준 온라인 저지에서 문제풀이를 연습하는데, 백준 온라인 저지의 문제들에는 난이도 표기가 없어서, 지금까지는 다양한 문제를 풀어 보고 싶더라도 난이도를 가늠하기 어려워 무슨 문제를 풀어야 할지 판단하기 곤란했기 때문에 solved.ac가 만들어졌다. solved.ac가 생긴 이후 전국에서 200명 이상의 기여자 분들께서 소중한 난이도 의견을 공유해 주셨고, 지금은 약 7,000문제에 난이도 표기가 붙게 되었다.

어떤 문제의 난이도는 그 문제를 푼 사람들이 제출한 난이도 의견을 바탕으로 결정한다. 난이도 의견은 그 사용자가 생각한 난이도를 의미하는 정수 하나로 주어진다. solved.ac가 사용자들의 의견을 바탕으로 난이도를 결정하는 방식은 다음과 같다.

• 아직 아무 의견이 없다면 문제의 난이도는 0으로 결정한다.
• 의견이 하나 이상 있다면, 문제의 난이도는 모든 사람의 난이도 의견의 30% 절사평균으로 결정한다.

절사평균이란 극단적인 값들이 평균을 왜곡하는 것을 막기 위해 가장 큰 값들과 가장 작은 값들을 제외하고 평균을 내는 것을 말한다. 30% 절사평균의 경우 위에서 15%, 아래에서 15%를 각각 제외하고 평균을 계산한다. 따라서 20명이 투표했다면, 가장 높은 난이도에 투표한 3명과 가장 낮은 난이도에 투표한 3명의 투표는 평균 계산에 반영하지 않는다는 것이다.

제외되는 사람의 수는 위, 아래에서 각각 반올림한다. 25명이 투표한 경우 위, 아래에서 각각 3.75명을 제외해야 하는데, 이 경우 반올림해 4명씩을 제외한다.

마지막으로, 계산된 평균도 정수로 반올림된다. 절사평균이 16.7이었다면 최종 난이도는 17이 된다.

사용자들이 어떤 문제에 제출한 난이도 의견 목록이 주어질 때, solved.ac가 결정한 문제의 난이도를 계산하는 프로그램을 작성하시오.

입력

출력

풀이방법

1. 입력을 모두 배열에 추가한다.

2. 배열을 정렬한다.

3. 범위를 지정하여 합을 구한다.

4. 합을 범위의 길이만큼으로 나눈다.

5.값을 정수형으로 출력한다.

* 여기서 파이썬의 round 함수의 오사오입과 사사오입 문제를 이해하고 따로 함수를 만들어 해결해야 한다. 그 방식에 대해서는 밑의 글에서 설명했다.

https://giliit.tistory.com/80

코드

# silver
# solved.ac
# 절사평균 30 : 위 15%, 아래 15%

import sys
from math import ceil, floor

# 파이썬의 사사오입, 오사오입 해결위한 방법
def custom_round(num):
    if num % 1 >= 0.5:
        return int(ceil(num))
    else:
        return int(floor(num))

def main():
    n = int(input())
    lst = []
    # 배열 입력
    for _ in range(n):
        tmp = int(input())
        lst.append(tmp)

	# 상위 15%와 하위 15% 수치를 구한다.
    k = int(custom_round(n * 0.15))
    
    # 배열을 정렬한다.
    lst.sort()
	
    # 0인 경우, 0 출력, 0이 아닌 경우, 값을 출력한다.
    if n == 0:
        print(0)
    else:
        print(int(custom_round(sum(lst[k:n-k])/(n-2*k))))



if __name__ == "__main__":
    input = sys.stdin.readline
    main()

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

문제

문자열 S가 주어졌을 때, S의 서로 다른 부분 문자열의 개수를 구하는 프로그램을 작성하시오.

부분 문자열은 S에서 연속된 일부분을 말하며, 길이가 1보다 크거나 같아야 한다.

예를 들어, ababc의 부분 문자열은 a, b, a, b, c, ab, ba, ab, bc, aba, bab, abc, abab, babc, ababc가 있고, 서로 다른것의 개수는 12개이다.

입력

출력

풀이방법

C++언에서 Substr을 이용해서 문자열을 slicing 한다. 이후에 set 자료구조를 이용해 중복을 제거하고 출련한다.

코드

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

int main()
{
  fastio;
  string str; cin>>str;

  set<string> sstr;

  for(int i=0;i<str.size();i++)
  {
    for(int j=1;j+i<=str.size();j++)
      sstr.insert(str.substr(i,j));
  }
  cout<<sstr.size();
}

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

문제

친구로부터 노트북을 중고로 산 스브러스는 노트북을 켜자마자 경악할 수밖에 없었다. 바탕화면에 온갖 파일들이 정리도 안 된 채 가득했기 때문이다. 그리고 화면의 구석에서 친구의 메시지를 확인할 수 있었다.

바탕화면의 파일들에는 값진 보물에 대한 정보가 들어 있어. 하나라도 지우게 된다면 보물은 물론이고 다시는 노트북을 쓸 수 없게 될 거야. 파일들을 잘 분석해서 보물의 주인공이 될 수 있길 바랄게. 힌트는 “확장자”야.

화가 났던 스브러스는 보물 이야기에 금세 화가 풀렸고 보물의 정보를 알아내려고 애썼다. 하지만 파일이 너무 많은 탓에 이내 포기했고 보물의 절반을 보상으로 파일의 정리를 요청해왔다. 스브러스의 요청은 다음과 같다.

• 파일을 확장자 별로 정리해서 몇 개씩 있는지 알려줘
• 보기 편하게 확장자들을 사전 순으로 정렬해 줘

그럼 보물의 절반을 얻어내기 위해 얼른 스브러스의 노트북 파일 정리를 해줄 프로그램을 만들자!

입력

출력

풀이방법

1. 파일을 파일이름과 파일 확장자로 나눈다.

2. 파일 확장자를 dictionary를 사용해 처음 나오는 확장자라면 value = 1을, 이전에 나온 확장자라면 value = value + 1

ex) 

3. 확장자(key)의 값들을 정렬한다.

4. 정렬된 확장자들을 차례대로 출력하면서 value값도 출력한다.

코드

# silver
# 파일 정리

import sys

def main():
    n = int(input())
    file = dict()
    
    # 파일이름과 파일 확장자로 나누는 코드
    for _ in range(n):
        file_name, file_extension = input().rstrip().split('.')
        
        # 처음나오는 확장자라면 dict에 추가
        if file_extension not in file:
            file[file_extension] = 1
        # 이전에 나온 확장자라면 dict에서 + 1을 한다.
        else:
            file[file_extension] += 1
    
    # key들을 정렬한다.
    file_extension_lst = sorted(file.keys())
    
    # key와 value들을 차례대로 출력한다.
    for i in file_extension_lst:
        print(f'{i} {file[i]}\n')

if __name__ == '__main__':
    input = sys.stdin.readline
    print = sys.stdout.write
    main()

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

문제

김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.

입력

출력

풀이방법

1. 듣도 못한 사람을 set에 추가한다.

2. 보도 못한 사람이 set에 있다면 KK 에 추가한다.

3. KK라는 요소들을 출력한다.

코드

#include<bits/stdc++.h>
using namespace std;


int main()
{
  int a,b;
  cin>>a>>b;
  set <string> K;
  
  // 듣도 못한 사람을 추가한다.
  while(a--)
  {
    string temp;  cin>>temp;
    K.insert(temp);
  }
  set<string> KK;
  // 보도 못한 사람이 듣도 못한 사람에 있다면 KK에 추가한다.
  while(b--)
  {
    string temp; cin>>temp;
    if(K.count(temp)) KK.insert(temp);
  }

  // 듣도 보도 못한 사람을 출력한다.
  cout<<KK.size()<<"\n";
  for(auto k : KK)
  {
    cout<<k<<"\n";
  }

}

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

문제

79를 영어로 읽되 숫자 단위로 하나씩 읽는다면 "seven nine"이 된다. 80은 마찬가지로 "eight zero"라고 읽는다. 79는 80보다 작지만, 영어로 숫자 하나씩 읽는다면 "eight zero"가 "seven nine"보다 사전순으로 먼저 온다.

문제는 정수 M, N(1 ≤ M ≤ N ≤ 99)이 주어지면 M 이상 N 이하의 정수를 숫자 하나씩 읽었을 때를 기준으로 사전순으로 정렬하여 출력하는 것이다.

입력

출력

풀이방법

1. N to M의 숫자를 문자로 변환하여 arr에 추가한다.

2. arr의 문자들을 알파벳 숫서대로 정렬한다.

3. 정렬한 arr의 문자들을 숫자로 변환한다.

4. 양식에 맞게 10개 출력 후 줄바꿈을 한다.

코드

# silver
# 숫자놀이

import sys

def main():
    num = ['zero ', 'one ', 'two ', 'three ', 'four ', 'five ', 'six ', 'seven ', 'eight ', 'nine ']
    num_dict = {'zero': '0','one':'1', 'two':'2','three':'3' , 'four':'4', 'five' : '5', 'six' : '6', 'seven': '7', 'eight' : '8', 'nine' : '9'}
    arr = []
    n, m = map(int, input().rstrip().split())
    
    # 숫자 -> 문자 변환
    for i in range(n,m+1):
        i_lst = list(str(i))
        i_str = ""
        for j in range(len(i_lst)):
            i_str += num[int(i_lst[j])]
        arr.append(i_str)
    
    # 문자 정렬
    arr.sort()

	# 문자 -> 숫자 변환 및 출력
    for i in range(len(arr)):
        a = arr[i].split()
        tmp = ''
        for k in a:
            tmp += num_dict[k]
        print(tmp+" ",end='')
        
        # 10개 출력 후 줄 바꿈
        if i % 10 == 9:
            print()


if __name__ == '__main__':
    main()

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

문제

두 단어 A와 B가 주어졌을 때, A에 속하는 알파벳의 순서를 바꾸어서 B를 만들 수 있다면, A와 B를 애너그램이라고 한다.

두 단어가 애너그램인지 아닌지 구하는 프로그램을 작성하시오.

입력

출력

풀이방법

2개의 문장을 정렬한다.

2개의 문장이 동일하다면 애너그램이며, 동일하지 않으면 애너그램이 아니다.

코드

# bronze
# 애너그램

import sys

def main():

    n = int(input())
    for _ in range(n):
        a, b = map(list,input().rstrip().split())
        a_sorted = sorted(a)
        b_sorted = sorted(b)
		
        # 정렬한 문장이 동일하다면
        if a_sorted == b_sorted:
            print(f"{''.join(a)} & {''.join(b)} are anagrams.")
		
        # 정렬한 문장이 동일하지 않다면
        else:
            print(f"{''.join(a)} & {''.join(b)} are NOT anagrams.")

if __name__ == '__main__':
    input = sys.stdin.readline
    main()

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

문제

라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다.

$4^2+3^2+1^2$ 으로 표현할 수도 있다.

역사적으로 암산의 명수들에게 공통적으로 주어지는 문제가 바로 자연수를 넷 혹은 그 이하의 제곱수 합으로 나타내라는 것이었다. 1900년대 초반에 한 암산가가

$15663=125^2+6^2+1^2+1^2$

라는 해를 구하는데 8초가 걸렸다는 보고가 있다. 좀 더 어려운 문제에 대해서는 56초가 걸렸다.

$11339=105^2+15^2+8^2+5^2$

자연수 n이 주어질 때, n을 최소 개수의 제곱수 합으로 표현하는 컴퓨터 프로그램을 작성하시오.

입력

출력

풀이방법

총 4가지 경우로 나뉜다.

1번째의 경우, 제곱수인 경우이다.

2번째인 경우, n = 제곱수 + 제곱수

3번째인 경우, n = 제곱수 + 제곱수 + 제곱수

4번째인 경우는 1, 2, 3번째 경우를 제외하고 이다. 

코드

import math

def main():
    n = int(input())
    squares = [i*i for i in range(1,224)]

    # 제곱 수가 있는 경우
    if n in squares:
        return 1

    for square in squares:
        if n-square  < 0:
            break
        if n-square in squares:
            return 2

    for square_1 in squares:
        if n-square_1 < 0:
            break
        for square_2 in squares:
            if n - (square_1 + square_2) < 0:
                break
            if n - (square_1 + square_2) in squares:
                return 3

    return 4

if __name__ == '__main__':
    print(main())