developer-ellen
인간 디버거의 로그 찍기
developer-ellen
전체 방문자
오늘
어제
  • 분류 전체보기 (217)
    • 회고록 (0)
    • 취뽀 및 커리어 여정의 Stack (2)
      • SSAFY 7기 (2)
    • 프로그래밍공부 (24)
      • c++ (0)
      • JAVA (3)
      • Spring (5)
      • design pattern (3)
      • BackDB (1)
      • Servlet&JSP (3)
      • Vue (4)
      • JPA (4)
      • Infra (1)
      • Linux (0)
    • AI (3)
      • papers (3)
      • trend (0)
    • 프로젝트진행 (0)
      • 데이터베이스 (0)
      • 서버개발 (0)
      • 인공지능 (0)
      • 하루정리 (0)
    • 포트폴리오 (0)
    • 알고리즘 (158)
      • 알고리즘문풀 (155)
      • 알고리즘공부 (3)
    • 통계공부 (15)
      • 시계열분석 (15)
      • 회귀분석 (0)
    • CS (14)
      • 컴퓨터네트워크 (4)
      • 운영체제 (8)
      • 데이터베이스 (2)
    • 주저리주저리 (0)
      • 필사 (0)
    • 취업관련정보 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • MA모형
  • 삼성코테파이썬풀이
  • 통계분석
  • 카카오코테java풀이
  • SW역량테스트파이썬풀이
  • 시계열분석
  • c++디자인패턴
  • 코테파이썬
  • 삼성코테자바꿀팁
  • 데이터분석
  • AR모형
  • c++ 빌더 패턴
  • 삼성코테자바풀이
  • ARIMA모형
  • 백준파이썬풀이
  • 삼성코테구현풀이
  • 시계열
  • 삼성코테파이썬
  • 삼성코테자바준비
  • SW역량테스트파이썬
  • 운영체제인터럽트
  • BOJ파이썬풀이
  • 카카오코테
  • 삼성코테파이썬준비
  • 통계학
  • 삼성코테기출
  • 삼성코테기출자바풀이
  • Arima
  • 삼성코테구현문제추천
  • 삼성코테준비

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
developer-ellen

인간 디버거의 로그 찍기

알고리즘/알고리즘문풀

BOJ - 마법사 상어와 파이어볼 20056번 (python)

2021. 10. 20. 22:23

❓ 문제 - 백준 마법사 상어와 파이어볼 20056번 - python 풀이법

 

출처 

(https://www.acmicpc.net/problem/20056)

 

20056번: 마법사 상어와 파이어볼

첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치

www.acmicpc.net

 

 

📝 문제해결법

1. 이 문제는 구현으로 풀었다.

  • board에 현재 파이어볼에 행과 열에 해당하는 정보(질량, 속력, 방향)을 저장한다.
  • move() 함수를 활용하여 k만큼 파이어볼을 이동시킨다.
  • board에 현재 남아있는 파이어볼의 질량합을 구해 출력한다.

2. move()

  • 파이어볼이 이동할 때 모든 파이어볼의 위치가 변경되므로 새로운 b 이중리스트를 이용하여 파이어볼 이동에 사용한다.
  • 현재 board에 파이어볼이 존재한다면, 해당 위치에서 방향으로 속력만큼 이동시켜 파이어볼을 위치시킨다.
  • b 이중리스트에 파이어볼이 2개 이상이라면 파이어볼을 합쳐야 한다. 파이어볼의 질량 합, 파이어 볼의 속력 합, 모두 홀수인지, 짝수인지를 구한다.
  • 만약 파이어볼의 합친 질량이 5 미만이라면 4개로 나누어질 때 질량이 모두 0 이하가 가 되므로 해당 파이어볼을 제거한다.
  • 만약 파이어볼의 합친 질량이 5 이상이라면 모두 방향이 홀수이거나, 모두 방향이 짝수일 때 방향을 0,2,4,6, 그외는 1, 3, 5, 7으로 해서 해당 행과 열에 파이어볼을 4개로 나눈 정보를 저장한다. 

 

3. 문제 풀면서 느낀점

  • 1번 행과 N번 행, 1번 열과 N번 열이 이어져 있으므로 이동 처리할 때 이동 후 칸 수 % N로 처리해야한다.

 

💻 소스코드

n, m, k = map(int, input().split())

dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]

board = [[[] for _ in range(n)] for _ in range(n)]

for i in range(m):
    r, c, mm, s, d = map(int, input().split())
    board[r-1][c-1].append([mm, s, d])
def move():
    b = [[[] for _ in range(n)] for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if len(board[i][j]) == 0:
                continue
            for p in board[i][j]:
                x, y = i, j
                mm, s, d = p
                nx = (x + dx[d]*s) % n
                ny = (y + dy[d]*s) % n
                b[nx][ny].append([mm, s, d])

    for i in range(n):
        for j in range(n):
            if len(b[i][j]) <= 1:
                continue
            mm_sum, s_sum, a_odd, a_even = 0, 0, True, True
            num = len(b[i][j])
            for p in b[i][j]:
                mm, s, d = p
                mm_sum += mm
                s_sum += s
                # 홀수
                if (d%2 == 1):
                    a_even = False
                else:
                    a_odd = False
            b[i][j] = []
            if mm_sum < 5:
                continue
            else:
                if a_odd or a_even:
                    for q in [0, 2, 4, 6]:
                        b[i][j].append([mm_sum//5, s_sum//num, q])
                else:
                    for q in [1, 3, 5, 7]:
                        b[i][j].append([mm_sum//5, s_sum//num, q])
    for i in range(n):
        for j in range(n):
            board[i][j] = b[i][j]


for _ in range(k):
    move()

answer = 0
for i in range(n):
    for j in range(n):
        for b in board[i][j]:
            answer += b[0]

print(answer)

'알고리즘 > 알고리즘문풀' 카테고리의 다른 글

BOJ - 마법사 상어와 파이어스톰 20058번 (python)  (0) 2021.10.21
BOJ - 마법사 상어와 토네이도 20057번 (python)  (0) 2021.10.21
BOJ - 컨베이어 벨트 위의 로봇 20055번 (python)  (0) 2021.10.20
BOJ - 스타트택시 19238번 (python)  (0) 2021.10.20
BOJ - 어른 상어 19237번 (python)  (0) 2021.10.20
    '알고리즘/알고리즘문풀' 카테고리의 다른 글
    • BOJ - 마법사 상어와 파이어스톰 20058번 (python)
    • BOJ - 마법사 상어와 토네이도 20057번 (python)
    • BOJ - 컨베이어 벨트 위의 로봇 20055번 (python)
    • BOJ - 스타트택시 19238번 (python)
    developer-ellen
    developer-ellen

    티스토리툴바