안녕

0. 문제 링크 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 1. 풀이 방법 코드에 모든 설명이 있음. 2. 코드 n, k = map(int, input().split()) board = [[b for b in map(int, input().split())] for _ in range(n)] w, v = [0] + [a for a, b in board], [0] + [b fo..

0. 문제 링크 https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 1. 풀이 방법 만약 2~4까지 펠린드롬이라고 가정해보자. 그러면 1~5까지 펠린드롬인지는 어떻게 알 수 있을까? 바로 1번째와 5번째가 맞는지 비교하고, 2~4가 펠린드롬인지 확인하면 되는 것이다. 따라서 n~m까지 펠린드롬인지 확인하기 위해서는, n-1~m-1이 펠린드롬인지 확인하고, n번째와 m번째가 펠린드롬인지 확인하면 된다. 숫자가 하나만 있는 경우는 무조건 펠린드롬이고, 2개가 있는 경우에는 맞는지 확인만 하..

0. 문제 링크 https://www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 1. 풀이 방법 i에서 j로 가는데, 기존에 점프한 횟수보다 i + 1이 더 적으면 가면 된다. dp 배열은 inf로 초기화 해야 한다. 이런 식으로 모든 i에 대해서, 점프할 수 있는 j를 찾아가며 초기화를 하면 결국 최소 횟수가 나오게 된다. 2. 코드 import sys n = int(sys.stdin.readline().strip()) board = [b for ..

0. 문제 링크 https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 1. 풀이 방법 그냥 전형적인 DP 문제이다. 보통 DP는 점화식만 잘 세우면 끝인데, 이 문제도 그렇다. dp 변수는 1부터 시작하지만, 사탕이 들어있는 맵인 board는 0부터 시작한다. 이거는 맞춰주면 된다. 참고로 대각선으로는 갈 필요가 없다. 왜냐하면 오른쪽 -> 아래로 가는 것이 대각선으로 가는 것인데, 이 방법이 대각선으로 직통으로 가는 것보다 훨씬 사탕..

0. 문제 링크 https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 1. 풀이 방법 2023.02.21 - [Computer Science/알고리즘] - [백준 - Python] 17141 - 연구소 2 공간을 다시 정의했다. 어차피 활성 바이러스 된다해도, 기존에 BFS에서 돌던게 있으니까 상관 없고, 결과적으로 진짜 비어있는 공간만 채우면 된다. 그래서 해당 글의 코드를 그대로 가져와서 그냥 공간만 다시 정의하고 제출했더니 성공; 2. 코드 import..

0. 문제 링크 https://www.acmicpc.net/problem/17141 17141번: 연구소 2 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이 www.acmicpc.net 1. 풀이 방법 우선 로봇 청소기에서 순열을 사용했던 것이 기억나서, 이번에는 조합을 이용하여 바이러스를 놔뒀다. 추가로 내가 얼만큼 공간을 채워야 하는지도 미리 파악했다. 만약 BFS가 끝났음에도 공간을 채우지 못했다면, -1을 출력하도록 처리했다. 2. 코드 import sys import itertools from collections import deque from copy impo..

0. 문제 링크 https://www.acmicpc.net/problem/17086 17086번: 아기 상어 2 첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸과 상어의 수가 각각 한 개 이상인 입력만 www.acmicpc.net 1. 풀이 방법 원래 이거 BFS로 풀어야 하는데, BFS로 풀기 싫었다. 그래서 다른 방법으로 풀었다. 어떤 좌표를 기준으로 특정한 크기의 정사각형을 슬라이싱을 한 후에, 거기에 1(상어)이 있다면 그 거리 최대 거리가 되는 것 만약 상어가 없다면 크기를 한 칸 늘려서 또 슬라이싱을 한다. 그렇게 최대 거리를 갱신한다. 그리고 그 다음 번에는 아까 ..

0. 문제 링크 https://www.acmicpc.net/problem/14395 14395번: 4연산 첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다. 연산의 아 www.acmicpc.net 1. 풀이 방법 해당 문제를 보면 알겠지만, 일단 뺄셈 연산은 쓰면 안 된다. 나눗셈 연산도 t가 2의 거듭제곱꼴이 아니라면 쓰면 안 된다. 사실상 연산은 +와 *만 하는 셈 그러면 숫자는 항상 우상향을 한다. 그래서 나는 t가 2의 거듭제곱꼴이 아니면 +와 *만 했고, 2의 거듭제곱이라면 / 연산도 추가했다. 근데 틀렸다. 솔직히 말해서 왜 틀린지 도저히 못찾았다. 결국 ..

0. 문제 링크 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 1. 풀이 방법 일단 해당 문제에서 가장 싫은 조건이 가장 위, 그런 것이 여러 마리라면 가장 왼쪽 이라는 조건이다. 먹이를 찾는다고 해서 끝이 아니라, 먹을 수 있는 먹이를 찾은 후에 거기서 조건을 통해 찾아야 하는 것 ! 아무튼 이 문제는 BFS를 상하좌우, 상좌우하 뭐 이렇게 한다고 해서 풀리지 않는다. ㅜㅜ 우선 먹이를 먹는 순간 방문 표시는 리셋 해야 하므로 원본 ..

0. 문제 링크 https://www.acmicpc.net/problem/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net 1. 풀이 방법 첫 번째로는 어떤 생각이 들었냐면, 내가 한 칸 올라가고 벽이 한 칸 내려오니까 사실상 내가 두 칸 올라가는 것은 아닐까? 라는 생각이 들었다. 근데 그건 귀찮을 것 같아서 그냥 넘겼고, 아무튼! 다른 생각을 했다. 이건 누구나 생각하겠지만, 내가 지금 가려는 곳이 벽이어서도 안 되고, 벽이 내려온 후에도 안전해야 한다. 사실 벽이 아래를 기준으로 한 칸..