BAEKJOON : 11399, 9663

Codren·2021년 9월 2일
0

No. 11399

1. Problem




2. My Solution

  • 뒤에 있는 사람은 무조건 앞에 있는 사람이 걸리는 시간만큼 기다림
  • 앞에 있는 사람이 적게 시간을 사용하면 적게 기다리고 많이 사용하면 많이 기다림
  • 앞에 1 걸리는 사람이 존재하면 뒤에 모두가 1초씩 기다리고 5 걸리는 사람이 존재하면 모두 5초씩 기다림
  • 오름차순 정렬
import sys

n = int(sys.stdin.readline())
people = list(map(int,sys.stdin.readline().rstrip().split()))
sum = 0
res = 0
people.sort()

for i in range(n):
    sum += people[i]
    res += sum

print(res)




No. 9663

1. Problem




2. Others' Solutions

  • 하나의 행에는 하나의 퀸만 놓을 수 있음 -> 각 행마다 퀸이 존재해야함
  • Permutation 수열 알고리즘 처럼 백트래킹을 이용
  • Python3 시간초과, PyPy3 통과
import sys
sys.setrecursionlimit(10**5)

# 대각선 방향 체크(Backtracking)
def check(r,c):
    for i in range(1,r+1):
        if board[r-i] == c-i or board[r-i] == c + i :
            return False
    return True

def dfs(row):
    global count

    if row >= n:
        count += 1
    else:
        for i in range(n):

            # 열 방향 체크(Backtracking)
            if col_visited[i] == True:
                continue
            else:
                if check(row,i) == True:
                    col_visited[i] = True
                    board[row] = i
                    dfs(row+1)
                    col_visited[i] = False

n = int(sys.stdin.readline())
board = [-1] * n
col_visited = [False] * n
count = 0

dfs(0)
print(count)




3. Learned

  • 참고 유튜브
  • 해당 자리에 퀸을 놓아도 되는지 check 하는 부분을 아래처럼 판단할 수도 있음
for i in range(r):
    if board[r] == board[i] or abs(board[r]-board[i]) == r-i:
       return False
    return True

0개의 댓글