BAEKJOON : 2231, 7568, 1018, 1436

Codren·2021년 6월 19일
0

No. 2231

1. Problem




2. My Solution

  • 5348 ms
import sys

n = int(sys.stdin.readline().strip())

flag = False

for i in range(n//2,n):
    if n == eval('+'.join(str(i))+"+i"):
        print(i)
        flag = True
        break

if flag == False:
    print(0)




3. Others' Solutions

  • 각 자리수의 최대 크기는 9이므로 자리수의 개수만큼 9를 뺀 값부터 판단
  • 68 ms
import sys

n = int(sys.stdin.readline().strip())

start = n - len(str(n))*9
if start < 18:
    start = 1

flag = False

for i in range(start,n):
    if n == eval('+'.join(str(i))+"+i"):
        print(i)
        flag = True
        break

if flag == False:
    print(0)




4. Learned

  • 결과를 만족하는 알고리즘을 구현했다면 그 다음은 수행시간을 줄일 수 있는 방법을 모색하자




No. 7568

1. Problem




2. My Solution

import sys

test_n = int(sys.stdin.readline().strip())
vol = []

for i in range(test_n):
    vol.append(list(map(int,sys.stdin.readline().strip().split())) + [0])

for i in vol:
    rank = 1
    for j in vol:
        if i[0] < j[0] and i[1] < j[1]:
            rank += 1
    i[2] = rank

for i in range(len(vol)):
    print(vol[i][2],end=" ")




No. 1018

1. Problem




2. My Solution

  • 비교할 W 시작 체스판, B 시작 체스판을 미리 만듬
  • 입력된 보드를 x,y 좌표로 접근하기 위해 2차원 행렬로 구현
  • 비교하는 chess_board 함수에 기준점이 되는 x,y 좌표값을 보냄
import sys

def chess_board(x,y):
    diff_w =0
    diff_b = 0

    for i in range(8):
        for j in range(8):
            if board[x+i][y+j] != start_w[i][j]:
                diff_w += 1
            if board[x+i][y+j] != start_b[i][j]:
                diff_b += 1  

    return min([diff_w,diff_b])


n,m = map(int,sys.stdin.readline().strip().split())
start_w = ["WBWBWBWB","BWBWBWBW","WBWBWBWB","BWBWBWBW","WBWBWBWB","BWBWBWBW","WBWBWBWB","BWBWBWBW"]
start_b = ["BWBWBWBW","WBWBWBWB","BWBWBWBW","WBWBWBWB","BWBWBWBW","WBWBWBWB","BWBWBWBW","WBWBWBWB"]

board = []
count = []

for i in range(n):
    board.append(sys.stdin.readline().strip())
 
for x in range(n-7):
    for y in range(m-7):
        count.append(chess_board(x,y))
    
print(min(count))




3. Others' Solutions

  • 0 1 2 3 4 5 6 7 에서 짝수 홀수 행과 열에 나타나는 색이 정해져있음, 이를 이용해서 w로 시작할 때 b로 시작할 때를 모두 비교
n, m = map(int, input().split())
l = []
mini = []

for _ in range(n):
    l.append(input())

for a in range(n - 7):
    for i in range(m - 7):
        idx1 = 0
        idx2 = 0
        for b in range(a, a + 8):
            for j in range(i, i + 8):              # 8X8 범위를 B와 W로 번갈아가면서 검사
                if (j + b)%2 == 0:
                    if l[b][j] != 'W': idx1 += 1  
                    if l[b][j] != 'B': idx2 += 1
                else :
                    if l[b][j] != 'B': idx1 += 1
                    if l[b][j] != 'W': idx2 += 1
        mini.append(idx1)                          # W로 시작했을 때 칠해야 할 부분
        mini.append(idx2)                          # B로 시작했을 때 칠해야 할 부분

print(min(mini))                                   # 칠해야 하는 개수의 최소값




4. Learned

  • 바보 같은 알고리즘이라도 일단 구현해보자. 결국엔 그게 최선일 수도 있다




No. 1436

1. Problem




2. My Solution

  • 입력값 n이 10000 까지 이므로 1씩 증가하여 비교하여도 1000ms
import sys

n = int(sys.stdin.readline().strip())

num = 666
death_num = 0
count = 0

while(True):

    if "666" in str(num):
        count += 1
    
    if n == count:
        print(num)
        break
    
    else:
        num += 1




3. Learned

  • 입력값의 범위를 보고 문제의 난이도를 판단한 뒤 알고리즘을 구현하자

0개의 댓글