은하철도999

제대로 된 설명이 없어서 내가 적는다!표를 그려놓은 글들은 모두 같은 글을 참고해서 그런가 표 자체에 요류가 있어서 날 헷갈리게 만들었다🥺 https://www.acmicpc.net/problem/18427    정리DP 사용가방 문제와 흡사완전 탐색으로 풀었다가 시간 초과 남!학생들을 반복하며 1부터 H 무게까지 만들 수 있는 경우의 수를 기록for문 3번 1. 학생들 반복2. 1부터 H 무게까지 반복3. 가지고 있는 블록만큼 반복0을 만들 수 있는 경우의 수는 무조건 0임! 그래서 1부터 반복 풀이1번째 학생 2번째 학생3번째 학생 import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.ArrayList;impo..

16437번: 양 구출 작전 (acmicpc.net) 16437번: 양 구출 작전 2, 3, 5번에 사는 모든 양들은 1번 섬으로 갈 수 있지만 7번 섬에 사는 양들은 1번 섬으로 가기 위하여 6번 섬을 거쳐야 하는데 6번 섬에 사는 늑대들의 수가 7번 섬에 사는 양들의 수보다 많으므로 www.acmicpc.net 풀이 처음에 모든 노드를 dfs를 해서 1번 노드를 만나면 결과를 더해주었다. 하지만, 시간초과가 떴고.... 결국 tree 구조를 사용해서 문제를 풀어주었다. 1번 노드와 연결된 노드만 방문하기 때문에 시간이 확실히 줄어든다. ** 연결된 노드가 양이면 결과를 더해주고 늑대면 빼줘야하는데, 만약 리프노드가 늑대이면 굳이 빼줄 필요가 없기 때문에 dfs에서 return을 통해 결과값에 더해주었..

14891번: 톱니바퀴 (acmicpc.net) 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 www.acmicpc.net 문제 4개의 톱니바퀴가 일렬로 놓여있다. 톱니바퀴 하나를 돌릴 때, 맞닿아있는 톱니바퀴와 극이 같으면 그대로 두고 극이 다르면 옆에 있는 톱니바퀴가 반대 방향으로 회전한다. 최종 톱니바퀴의 상태 구하기 풀이 특별한 알고리즘 없이 구현하는 문제였다. 나는 톱니바퀴가 회전하는 효과를 주기 위해 pivot이라는 배열을 만들어서 각 톱니바퀴의 12시 방향에 있는 index를 담아주었다. 시계방향으로 회전한다면 pivo..

1405번: 미친 로봇 (acmicpc.net) 1405번: 미친 로봇첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자www.acmicpc.net 문제로봇이 갔던 곳을 다시 방문하지 않을 확률 구하기 해석이동경로가 단순할 확률 구하기 방문하지 않은 곳만 N번 방문했을 때의 확률을 모두 더해주면 되는 문제이다. 행동의 횟수만큼 100으로 나누어서 확률을 구해준다.import sys sys.setrecursionlimit(10**6) n, E, W, S, N = map(int,input().split()) direction = [E,W,S,N] #동 서 남 북 ..

11559번: Puyo Puyo (acmicpc.net) 11559번: Puyo Puyo총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net문제같은 색상 4개가 모이면 없어진다. => 1연쇄(한 타임에 한 번) 위에 있는 뿌요가 아래가 빈칸이면 내려온다. 총 몇 번의 연쇄가 일어날까? 해석bfs로 같은 색상의 뿌요를 찾아주었다. 4개 이상의 뿌요가 모이면 터지기 때문에 뿌요의 index를 저장할 배열을 따로 만들어 주었다 뿌요가 터지면, 가장 밑에서부터 위로 올라가면서 뿌요가 내려올 수 있을 때까지 내려주었다. from c..

17142번: 연구소 3 (acmicpc.net) 17142번: 연구소 3인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고www.acmicpc.net해석바이러스 중 몇개를 뽑아 빈칸을 모두 바이러스로 확진시키기!! 0은 빈 칸, 1은 벽, 2는 바이러스 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간은? 풀이우선, 조합을 사용해서 활성 바이러스 배열을 만들었다 이 조합을 이용해 bfs를 돌려 모든 빈칸이 바이러스가 확진되는 시간을 구하였다. from collections import deque import sys input = sys.stdin.readline N,M = map..

2981번: 검문 (acmicpc.net) 2981번: 검문트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간www.acmicpc.net문제숫자 N개를 종이에 적는다. 그 다음, 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다. M은 1보다 커야 한다. N개의 수가 주어졌을 때, 가능한 M을 모두 찾는 프로그램을 작성하시오. 풀이모든 수를 for문으로 돌렸을 때 시간 초과..!! (해결) 입력 값들의 차의 최대 공약수를 구하고 이 최대 공약수의 약수를 구하면 되는 문제 A = gcd *a + mod B = gcd*b + mod C =..

2225번: 합분해 (acmicpc.net) 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오. (덧셈의 순서가 바뀐 경우는 다른 경우) 풀이 dp[k][n] = dp[k-1][0] + dp[k-1][1] + dp[k-1][2] + . . . + dp[k-1][n-1] + dp[k-1][n] 대입 dp[k][n-1] = dp[k-1][0] + dp[k-1][1] + dp[k-1][2] + . . . + dp[k-1][n-1] 점화식 : dp[k][n] = dp[k-1][n] + dp[k][n-1] import sys input = sys..

1669번: 멍멍이 쓰다듬기 (acmicpc.net) 1669번: 멍멍이 쓰다듬기 동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다 오늘도 어김없이 그의 영원한 라이벌 멍멍이를 만나게 되었다. 원숭이는 멍멍이를 쓰다듬고 싶었다. 하지만 원숭이는 멍 www.acmicpc.net 문제 원숭이는 초능력자이기 때문에 마음대로 키를 늘릴 수 있다. 하지만 안타깝게도 사람이 아니라 동물이기 때문에 하루에 늘릴 수 있는 키의 양을 1cm밖에 조절할 수 없다. 첫째 날과 마지막 날에는 무조건 1cm 만큼 늘릴 수 있다. 현재 원숭이와 멍멍이의 키가 주어졌을 때, 원숭이가 매일 키를 늘려서 멍멍이와 키가 같아지는 최소의 일수는? monkey,dog = map(int,input().split()) di..

4811번: 알약 (acmicpc.net) 4811번: 알약입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다.www.acmicpc.net 문제첫째 날에 약을 반으로 쪼개서 한 조각은 먹고, 다른 조각은 다시 병에 넣는다. 다음 날부터 반 조각이라면 그 약을 먹고, 아니라면 반을 쪼개서 한 조각을 먹고, 다른 조각은 다시 병에 넣는다. 한 조각을 꺼낸 날에는 W, 반 조각을 꺼낸 날에는 H 총 2N일이 지나났을 경우, 가능한 서로 다른 문자열의 개수는?? 풀이2차원 dp를 이용해서 풀어야 하는 문제 dp[i][j] : 알약 반 개를 i개 먹고, 알약 한 개를 j개 먹었을 때의..