https://www.acmicpc.net/problem/15990 코드dp = [[0]*3 for _ in range(100001)] # 1열은 이번에 1 더했을 때, 2열은 2, 3열은 3 더했을 때dp[1][0] = 1dp[2][1] = 1dp[3] = [1, 1, 1]for i in range(4, 100001): dp[i][0] = (dp[i-1][1]+dp[i-1][2]) % 1_000_000_009 dp[i][1] = (dp[i-2][0]+dp[i-2][2]) % 1_000_000_009 dp[i][2] = (dp[i-3][0]+dp[i-3][1]) % 1_000_000_009for _ in range(int(input())): n = int(input()) pr..
문제풀이
https://www.acmicpc.net/problem/2589 코드from collections import dequeimport sysinput = sys.stdin.readliner, c = map(int, input().split())board = [input() for _ in range(r)]def bfs(x, y): # (x, y)에서 이동할 수 있는 육지 중 가장 먼 곳까지의 이동 시간 dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] max_dist = 0 visited = [[False]*c for _ in range(r)] visited[x][y] = True q = deque([(x, y, 0)]) while q: ..
https://www.acmicpc.net/problem/20116 코드n, l = map(int, input().split())x = list(map(int, input().split()))center = x[-1] # 무게 중심num = 1for i in range(n-2, -1, -1): if center = (x[i]+l): print("unstable") exit() center = ((center*num)+x[i])/(num+1) # 위에서부터 i번째까지의 무게 중심 num += 1 # i번째까지 상자 개수print("stable") i번째보다 높은 상자들의 무게 중심이 i번째 상자 안에 있는지 판별해야 하므로 위에서부터 내려와야 한다. 우..
https://www.acmicpc.net/problem/20115 코드n = int(input())drinks = list(map(int, input().split()))drinks.sort()ans = drinks[-1]for i in range(len(drinks)-1): ans += (drinks[i]/2)print(ans) 처음에는 남은 음료들 중 가장 양이 적은 2개를 골라서 합쳐야 하는줄 알았는데, 아니었다. 매 순서에 2로 나누어지는 음료들을 최대한 작게 해주어야 하는데, 이렇게 하면 그럴 수 없다.예를 들어, 음료 5개가 가장 작은 것부터 순서대로 a, b, c, d, e 이렇게 있다고 하면 원래 생각한 방법대로면 처음에 a, b를 뽑아서 (a/2)+b를 만들게 된다. 그 다음 순서..
https://www.acmicpc.net/problem/10867 코드#include #include using namespace std;int main(){ int n; cin >> n; set s; int tmp; for(int i=0;i::iterator iter=s.begin();iter!=s.end();iter++){ printf("%d ", *iter); } return 0;} 이 문제는 집합을 이용하여 풀면 쉽게 풀 수 있다. 다행히 C++에는 집합이 이미 구현되어 있기 때문에 가져다 쓸 수 있다.#include 집합에 입력받은 수들을 넣었다가 출력해주기만 하면 되는데, set은 기본적으로 원소를 넣을 때마다 정렬되어서 삽입되므로 정렬해줄 ..
