본문 바로가기

⭐ Problem_Solving/백준30

[백준] 1799 비숍 (Python/파이썬) https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 1. 백트래킹으로 푸는 문제지만 단순하게 구현하면 시간초과가 나기 때문에 최적화를 하기 위한 아이디어가 필요한 문제입니다. 2. 대각선으로만 움직이는 비숍의 특징을 고려할 때 검은색 칸에 놓인 비숍은 검은색 칸으로만 움직일 수 있고 하얀색 칸에 놓인 비숍은 하얀색 칸으로만 움직일 수 있습니다. 3. 따라서 검은색과 하얀색 각각의 칸에 대해 비숍을 놓는 경우의 수를 따로 구해서 더해주는 방식으로 최적화를 할.. 2023. 6. 5.

[백준] 20165 인내의 도미노 장인 호석 (Python/파이썬) https://www.acmicpc.net/problem/20165 20165번: 인내의 도미노 장인 호석 사람을 화나게 하는 법은 다양하다. 그 중에서도 악질은 바로 열심히 세워놓은 도미노를 넘어뜨리는 것이다. 이번에 출시된 보드 게임인 "너 죽고 나 살자 게임"은 바로 이 점을 이용해서 2명이 www.acmicpc.net 1. 무난한 구현 문제로 수비와 공격 함수를 구현하면 됩니다. 2. 공격 함수는 재귀적으로 구현하였으며 이미 넘어진 블럭과 범위를 잘 확인해서 구현하면 됩니다. import sys, os, io, atexit input = lambda: sys.stdin.readline().rstrip('\r\n') stdout = io.BytesIO() sys.stdout.write = lambd.. 2023. 5. 14.

[백준] 1421 나무꾼 이다솜 (Python/파이썬) https://www.acmicpc.net/problem/1421 1421번: 나무꾼 이다솜 첫째 줄에 이다솜이 가지고 있는 나무의 개수 N과 나무를 자를 때 드는 비용 C와 나무 한 단위의 가격 W이 주어진다. 둘째 줄부터 총 N개의 줄에 이다솜이 가지고 잇는 나무의 길이가 한 줄에 하나 www.acmicpc.net 1. 기본적으로 나무가 50개 이하고 나무 길이가 10000이하라서 O(N^2)여도 대략 50 * 10000 = 50만 번 연산을 해서 완전 탐색으로 풀 수 있습니다. 2. 길이가 1부터 가장 긴 나무까지 모두 잘라보며 최대 이익을 구하면 되는데 2가지 함정이 있습니다. 3. 첫째, 나무가 남는 부분 없이 딱 잘릴 경우에는 잘린 횟수를 1 빼줘야됩니다 (ex 길이가 8인 나무를 2의 길이로.. 2023. 5. 8.

[백준] 27942 :danceplant: (Python/파이썬) https://www.acmicpc.net/problem/27942 27942번: :danceplant: 첫째 줄에 가지가 몸을 늘이며 먹은 양분의 총량을 출력한다. 둘째 줄에 가지가 몸을 늘인 방향을 나타내는 문자를 늘인 순서대로 한 줄에 출력한다. 상하좌우는 각각 UDLR에 대응된다. www.acmicpc.net 1. 시뮬레이션 / 누적합 문제입니다. 2. java나 c++은 단순 구현으로도 통과가 될 것 같은데 python기준으로는 시간초과가 발생하고 pypy로 통과가 됩니다. 3. 저는 단순 시뮬레이션으로 풀었지만, 누적합 알고리즘을 활용해 초기에 입력 받은 배열을 누적합 배열로 변환하고 영양분 섭취를 일일히 더하는 게 아니라 해당 행 / 열에서 구간합만 더해주면 파이썬으로도 시간 내에 통과가 될.. 2023. 4. 12.

[백준] 17070 파이프 옮기기1 (Python/파이썬) https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 1. 2차원 배열에서 도착지까지의 경로의 개수를 찾는 유형의 DP 문제이지만 N의 범위가 작아 BFS로도 풀 수 있습니다. 2. 저는 DP로 풀었으며 테이블은 각 좌표마다 해당 좌표를 끝점으로 하는 파이프가 놓일 수 있는 경우의 수를 각 방향(가로, 세로, 대각선)에 대해 계산한 배열로 정의했습니다. 3. 해당 좌표와 직전 좌표의 벽 여부를 검사하면서 테이블을 채워 나가면.. 2023. 4. 4.

[백준] 2072 오목 (Python/파이썬) https://www.acmicpc.net/problem/2072 2072번: 오목 19x19크기의 바둑판에, 돌을 놓을 좌표가 주어지면 이 게임이 몇 수만에 끝나는 지를 알아보려고 한다. 사용하고자 하는 바둑판의 모양은 위의 그림과 같으며, (1, 1)이 가장 왼쪽 위의 좌표이고 (19 www.acmicpc.net 1. 오목 여부 검증 함수를 만들어서 수를 둘 때마다 검증하면 된다 2. 행, 열, 두 대각선에 대해 구현하면 된다. 3. 육목이랑 0 index 조심하기 4. bfs나 dfs 혹은 그냥 델타 탐색으로도 풀 수 있는데 생각하기 귀찮아서 빡구현으로 풀었다(코드는 전자가 더 깔끔하다) import sys, os, io, atexit input = lambda: sys.stdin.readline(.. 2022. 12. 28.

이전 1 2 3 4 5 다음

티스토리툴바