문제 설명 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 성능 요약 메모리: 40628 KB, 시간: 148 ms 분류 다이나믹 프로그래밍 제출 일자 2024년 3월 6일 01:34:27 문제 설명 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽..
알고리즘/백준
문제 설명 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 문제 풀이 사실 문제에서 나온 대로 구현만 하면 되는데 좌표가 자꾸 헷갈려서 오래 걸렸던 문제.. 그래도 이 문제를 풀고 나니 좌표에 대한 감이 어느정도 잡혔다 n, m = list(map(int, input().split())) r, c, d = list(map(int, input().split())) board = [list(map(..
문제 설명 https://www.acmicpc.net/problem/2564 2564번: 경비원 첫째 줄에 블록의 가로의 길이와 세로의 길이가 차례로 주어진다. 둘째 줄에 상점의 개수가 주어진다. 블록의 가로의 길이와 세로의 길이, 상점의 개수는 모두 100이하의 자연수이다. 이어 한 줄 www.acmicpc.net 문제 풀이 처음에는 2차원 배열로 풀라고 했는데... 배열 인덱스들이 너무 헷갈려서 끙끙대고 있을 때 같이 푸는 친구에게 아이디어를 듣고 풀어보았다 2차원 배열로 생각하지 말고, 사각형을 일자로 쭉- 펴서 풀어보라는 것 그렇게 1차원 배열로 생각해서 풀었더니 쉽게 풀렸다! w, h = list(map(int, input().split())) n = int(input()) store = [li..
문제 설명 https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 문제 풀이 시간초과 때문에 힘들었던 문제.. 이게 파이썬의 한계인가 처음에는 count가 n일 때 route 배열에 있는 순서대로 cost를 더해주면서 값을 구하고, 총 비용과 minCost를 비교하는 방법으로 코드를 짰었는데 시간초과가 걸렸다 파라미터로 cost를 더하면서 넘겨주고 minCost와 파라미터로 넘어온 cost를 비교해서 더 낮..
문제 설명 https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 문제 풀이 turn 메소드를 통해 반시계 방향과 시계 방향으로 돌려주는 작업을 해주었다. 인덱스로 확인하기 때문에 회전하는 톱니를 받고 -1를 해주었고(n -= 1) d 배열로 톱니마다 방향을 저장해주었다. 처음에는 if문으로 1번 톱니일 때, 2번 톱니일 때,,, 하나씩 처리해주려고 했는데 if문 중첩이 너무 많아져서 어지럽길래 다른 방법을 생각해보았다. 왼쪽으로 확인해야 될 톱니..
문제 설명 https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 문제 풀이 1로 만들기와 똑같은 문제인데 여기서는 과정을 출력해야 한다 (경로 추적) 처음에는 i마다 i를 1로 만드는 과정들을 2차원 배열로 저장하고, 이전 단계의 배열을 복사해와서 거기에 append를 통해 모든 i의 과정을 저장하는 방법을 사용하였다 n까지 다 구해지면 n을 1로 만드는 과정이 담긴 배열을 reverse 한 후 len과 함께 출력했는데 시간초과... 아마 배열을 복사하는 과정에서 시간초과가 났던 것 같다 시간 초과가 나와서 다른 방법을 생각했다 어디서 왔는지 경로를 추적..
문제 설명 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 풀이 처음에 테이블을 생각할 때 최소비용을 저장하는 1차원 배열로 정의해서 점화식을 생각해봤는데 아무리 생각해도 점화식 구하기 너무 힘들 것 같아서 2차원 배열로 정의했다 점화식 d[i][0] = min(d[i - 1][1], d[i - 1][2]) + cost[i][0] d[i][1] = min(d[i - 1][0], d[i - 1][2]) + cost[i]..
문제 설명 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 풀이 점화식 구하기 2번째 전 계단을 밟는 경우 => D[i - 2] + floor[i] 1번째 전 계단을 밟는 경우 (연속된 세 계단을 밟으면 안 되기 때문에 3번째 계단을 밟고 1번째 전 계단으로 올라와야 한다) => D[i - 3] + floor[i - 1] + floor[i] 이 두 경우 중 최댓값이 D[i]이 된다! 점화식 : D[i] = max(D[i - 2] + floor[i], ..
문제 설명 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제 풀이 점화식 구하는 것에 익숙해지려고 쉬운 DP 문제부터 푸는 중 .. 예시에 나온 D[4]를 봤을 때 1 + 1 + 1 + 1, 1 + 2 + 1, 2 + 1 + 1, 3 + 1 => 3을 1, 2, 3의 합으로 나타내는 법 + 1 1 + 1 + 2, 2 + 2 => 2를 1, 2, 3의 합으로 나타내는 법 + 2 1 + 3 => 1을 1, 2, 3의 합으로 나타내는 법 + 3 점화식 : D[i] = D[i - 1] + D[i - 2] + D[i - 3] 초기값 : D[1] =..
문제 설명 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제 풀이 이 문제는 BFS, DFS 두 방법 다 사용 가능하다 그래서 두 가지 방법으로 풀어보았다! 1. DFS 배추가 심어진 땅의 개수를 구하는 것이기 때문에 가장 먼저 DFS로 푸는 방법을 떠올렸다 재귀를 돌면서 아직 방문하지 않았으면서 값이 1인 부분을 찾고, 재귀가 끝나면 return True를 해준다 반복문으로 dfs 함수를 호출해 true면 result를 증가해준다 import sys ..
