Seongkyun Han's blog

190108 백준 알고리즘 문제풀기

08 Jan 2019 | baekjoon

Baekjoon 알고리즘 문제풀기

[1065] 한수

문제

  • 어떤 의 정수 N의 각 자리수가 등차수열을 이루면 그 수를 한수라고 함

  • N이 주어졌을 때, 1부터 N까지의 한수의 갯수를 출력하는 프로그램 작성

  • 1~99까지의 모든 수는 한수이므로 이를 고려하여 풀면 더 쉽게 풀 수 있다.
  • 각 자리수가 등차수열을 이룬다면 모든 자릿수간의 차가 동일할것이므로, 1번째 차인 subs[0]의 갯수가 len(subs)와 동일해야 하는 점을 이용했다.

정답

def one_num(a):
    subs = []
    for j in range(0, len(a)-1):
        sub = int(a[j])-int(a[j+1])
        subs.append(sub)
    if subs.count(subs[0]) == len(subs):
        return 1
    else:
        return 0

a = int(input())

if a<100:
    print(a)
else:
    cnt = 99
    for j in range(100, a+1):
        cnt += one_num(str(j))
    print(cnt)

[2448] 별 찍기 - 11

문제

  • 예제를 보고 규칙을 유추한 뒤 별을 찍는다.
  • N은 항상 $3*2^k$수 이며, $k<=10$의 조건을 만족한다.

예제출력 (입력: 24)


                       *                        
                      * *                       
                     *****                      
                    *     *                     
                   * *   * *                    
                  ***** *****                   
                 *           *                  
                * *         * *                 
               *****       *****                
              *     *     *     *               
             * *   * *   * *   * *              
            ***** ***** ***** *****             
           *                       *            
          * *                     * *           
         *****                   *****          
        *     *                 *     *         
       * *   * *               * *   * *        
      ***** *****             ***** *****       
     *           *           *           *      
    * *         * *         * *         * *     
   *****       *****       *****       *****    
  *     *     *     *     *     *     *     *   
 * *   * *   * *   * *   * *   * *   * *   * *  
***** ***** ***** ***** ***** ***** ***** *****

정답 1(시간초과)

  • 시간초과가 발생하므로 다른 풀이가 필요하다.
  • 별 크기만큼의 도화지(paper 배열)를 설정하고, 거기에 별을 찍는 방식이다.
  • 첫 번째 별의 좌표만 입력하면 재귀함수를 이용하여 별을 그린다.
def draw(line, x, y):
    global paper
    if line==3:
        paper[y][x] = '*'
        paper[y+1][x-1] = '*'
        paper[y+1][x+1] = '*'
        paper[y+2][x-2] = '*'
        paper[y+2][x-1] = '*'
        paper[y+2][x] = '*'
        paper[y+2][x+1] = '*'
        paper[y+2][x+2] = '*'
        return
    draw(line/2, x, y)
    draw(line/2, x-int(line/2), y+int(line/2))
    draw(line/2, x+int(line/2), y+int(line/2))

a = int(input())

rows = a
cols = a * 2 - 1
global paper
paper = [[' ' for j in range(cols)] for i in range(rows)]

draw(a, a-1, 0)
for j in range(0, rows):
    for i in range(0, cols):
        print(paper[j][i], end='')
    print('')

정답 2

  • 기본 삼각형을 만든 후, shifting 시키면서 이어붙여 출력시킨다.
  • 삼각형의 제일 꼭지 별을 다음 삼각형에서 얼마나 밀어내야 하는지($k$)에 대한 규칙 발견이 필요하다.
  • N이 3, 6, 12, 24… 일때 각각 $k$는 0, 3, 6, 12… 씩 증가한다.
  • 주어지는 수 N이 $N=3*2^{k}$ 의 조건을 따름
  • $3*2^{N-1}$ 만큼씩 오른쪽으로 shifting 시켜야 한다.
  • 따라서 $N=3*2^k$의 양 변에 $log$ 를 씌우면, $k=\log_2{\frac{N}{3}}$ 가 성립한다.
  • 이를 이용하여 삼각형을 shifting하며 이어붙여 정답을 출력한다.
import math

global tri
tri = ['  *   ', ' * *  ', '***** '] # 기본 삼각형

def shift(k):
    global tri
    for j in range(len(tri)):
        tri.append(tri[j]+tri[j]) # 이전 삼각형 뒤에 현 단계 삼각형을 붙이고
        tri[j] = (' '*3*k+tri[j]+' '*3*k) # 계산된 k만큼 현 단계 삼각형을 민다.

a = int(input())
k = int(math.log(int(a / 3), 2))
for j in range(k):
    shift(int(pow(2, j)))

for j in range(a):
    print(tri[j])
  • 지금까지 풀었던 문제 중 가장 까다로웠던 것 같다…

[1152] 단어의 개수

문제

  • 입력된 문장의 단어의 갯수를 출력

정답

a = list(map(str, input().split()))

print(len(a))

[2577] 숫자의 개수

문제

  • 세 개의 자연수 a, b, c에 대해 세 수가 곱해진 결과에 0부터 9까지의 숫자가 몇개씩 존재하는지를 나란히 출력

정답

a = int(input())
b = int(input())
c = int(input())

nums = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
result = str(a * b * c)

for j in range(0, len(result)):
    for i in range(0, 10):
        if int(result[j]) == i:
            nums[i] += 1

for j in range(0, 10):
    print(nums[j])

Related Posts