Dogfootruler Kim

문제 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 풀이 및 소스코드 dp[n] = dp[n-2]+dp[n-3] 이라는 규칙이 있다. n이 100까지이므로 dp 배열은 long으로 해줘야 한다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; class Main { public static void main(String[] args..

문제 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 및 소스코드 조합(combi) 을 통해서 세울 벽 3개를 고르는 경우의 수를 구한 후, 그에 대해 bfs를 진행해서 바이러스를 퍼뜨려주었다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.LinkedL..

문제 https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 풀이 및 소스코드 맥주를 마시면서 이동할 수 있는 거리는 50*20 = 1000 이다. 좌표들을 입력받고, 그 좌표들끼리 사이의 거리가 1000이하라면 서로 갈 수 있는 곳이기 때문에 정점을 양방향으로 연결해준다. 연결해준 정점을 토대로 집(g[0])부터 시작해서 bfs를 돌린다. 도착지 인덱스인 n+1에 도달하면 happy를, 도달하지 않는다면 sad를 출력해주면 된다. import ..

풀이 및 소스코드 LIS(Longest increasing Subsequence)란, 가장 긴 증가하는 부분 수열이다. 예를 들어, [6, 2, 5, 1, 7, 4, 8, 3] 이라는 배열이 있을 경우, LIS는 [2, 5, 7, 8]이 된다. 증가하는 부분 수열 중 가장 긴 것이기 때문. LIS를 풀기 위한 가장 일반적인 방법은 DP를 이용하는 것이다. [100, 50, 70, 90, 75, 87, 105, 78, 110, 60] 이 배열의 LIS를 구한다고 가정해보면, LIS는 [50, 70, 75, 87, 105, 110] 로, 길이는 6이 된다. 아래와 같은 순서로 진행된다. [0] [0, 100] [0, 50] [0, 50, 70] [0, 50, 70, 90] [0, 50, 70, 75] [0,..

문제 https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 풀이 및 소스코드 왜 말이 되고픈지 모르겠당.. 넘 어려웠다. k별로도 방문체크를 해줘야했기때문에 인생 최초로 3차배열에 방문표시를 해줬다. 이 때문에 푸는 게 오래걸린 것 같다. 처음에 dfs로 풀려고 했으나, 시간초과가 났다. bfs로 바꿨는데 6%에서 자꾸 틀렸다고 했다. 현재 좌표에 대한 k_cnt 값을 고려해주지 않고, 그저 k 만 넘지 않았으면 시간 비교를 해줬기 ..

MST는 프림과 크루스칼 알고리즘을 이용하여 풀면 된다. 나는 항상 크루스칼으로 풀어왔기 때문에 이번엔 프림으로 풀어봤다 ! 여기서 주의할 점은, C는 음수일 수도 있으며, 절대값이 1,000,000을 넘지 않는다. 이 문장이다. 나는 그래서 결과 값을 long으로 선언해줬다. int 로 하니 10개의 테케가 전부 틀려버림 ... import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.PriorityQueue; import java.util.StringTokenizer; public class Solution { p..

문제 https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 풀이 및 소스코드 https://jainn.tistory.com/261 [백준] 2638번:치즈 (Java 자바) 문제 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는.. jainn.tistory.com 이처럼 풀되..

문제 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 및 소스코드 dp 배열은 dp[n][0] : n번째에서 R을 선택한 경우 dp[n][1] : n번째에서 G을 선택한 경우 dp[n][2] : n번째에서 B을 선택한 경우 를 의미한다. dp[0]은 {0,0,0} 이 담겨있기 때문에 i를 1부터 시작해도 상관없다. dp[n][0] 은 n번째에서 R을 선택한 경우라고 앞서 말했기 때문에, n-1번째에서 G, B를 선택한..