본문 바로가기

알고리즘60

[Python] 백준 11049: 행렬 곱셈 순서 https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 1. ABCD 의 행렬이 주어졌을경우 행렬은 A(BCD), (AB)(CD), (ABC)D 총 4가지 경우의 수가 나오고 A(BCD)의 경우 BCD = B(CD), (BC)D 로 다시 쪼개진다. 2. 행렬은 r * c 이므로 각 행렬의 항을 a항에 넣어주면 점화식은 dy[s][e] = dy[s][k] + dy[k][e] + a[s]*a[k]*a[e] (s+1 2021. 10. 2.
[Python] 백준 17070: 파이프 옮기기 1 https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 1. dp로 푸는 문제이다. (n, n) 좌표로 올수있는 방법은 대각선, 가로, 세로 총 3가지이다. 2. dy배열에 가로(0), 세로(1), 대각선(2)으로 올수있는방법 + 각 좌표의 방법으로 3차원배열을 만든다. 3. 가로 2가지, 세로 2가지, 대각선3가지 이고 대각선일때는 현재좌표와 (x-1, y), (x, y-1) 좌표가 벽으로 막혀있으면 안된다. 4. dfs를 .. 2021. 10. 2.
[Python] 백준 1132: 합 https://www.acmicpc.net/problem/1132 1132번: 합 N개의 숫자가 주어진다. 이 숫자는 모두 자연수이고, 알파벳 A부터 J가 자리수를 대신해서 쓰여 있다. 이 알파벳은 모두 한 자리를 의미한다. 그리고, 각 자리수는 정확하게 알파벳 하나이다. 0으 www.acmicpc.net 1. ABC, BCA의 경우 101A + 110B + 11C 이므로 9부터 1까지 역으로 정렬후 곱해주면 된다. 2. a 배열의 1번째 값은 알파벳의 자리의 합 2번째는 알파벳이 맨 앞에인지 확인하는 값이다. 3. 만약 정렬후 마지막 값이 앞에 존재할경우 가장 가까운값 중에 앞에 존재하지 않는 값기준으로 땡겨준다. ex) AB BCD CDE DEF EFG FGH GHI HIJJJ의 경우 A값이 앞에 있.. 2021. 9. 29.
[Python] 백준 17371: 이사 https://www.acmicpc.net/problem/17371 17371번: 이사 $(\frac{2}{3}, \frac{1}{3})$으로 이사를 가면 가장 가까운 편의시설은 (0, 1)으로 거리는 $\frac{2\sqrt{2}}{3}$이고, 가장 먼 편의시설은 (-4, 1) 혹은 (4, -3)으로 거리는 둘 다 $\frac{10\sqrt{2}}{3}$이다. 두 거리의 www.acmicpc.net 1. 현재 좌표를 기준으로 가장 긴 선분을 찾는다. (가장 가까운 곳과 가장 먼 곳을 찾아야 하므로. 현재 지점이 가장 가까운 곳이고 또 다른 좌표가 가장 먼 곳이다.) 2. 이 선분들 중에서 가장 짧은 선분을 찾는다. 좌표는 그 선분 사이 아무 좌표나 가능하다.(직선일 때가 가장 최소의 길이므로 이 (x1.. 2021. 9. 27.

티스토리툴바