6-6화이탱

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net dp 문제로, n번째 계단의 최대 값은 1) n -1번째 계단을 밟고 n-3번째 계단을 밟은 것 , 2) n-2번째 계단을 밟은 것 이다. 예를 들어 4번째 계단의 최대값은 1) 3번째 계단과 1번째 계단 값 ㅁ ㅁ ㅁ ㅁ 2) 3번째 계단과 4번째 계단 값 ㅁ ㅁ ㅁ ㅁ 이다. import java.io.BufferedReader; import java.io.IOException; import java.io..

https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net dp를 사용해서 해결할 수 있었다. ㅁㅁㅁㅁ ㅁㅁㅁㅁ ㅁㅁㅁㅁ ㅁㅁㅁㅁ 이런식으로 왼쪽, 위, 왼쪽 대각선 부분을 확인하여 해당 위치들에서 가장 작은 값에 +1한 값을 넣는다. 그리고 그 값이 가장 큰 값인지 확인한다. ex) 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 인덱스의 시작은 (1,1) 이다! (1,1)에 1이 존재하므로, 왼쪽, 위, 왼쪽 대각선을 확인한다. -> 다 0이므로 0+1 값을 넣는다. (1,2)에 1이 존재하므로, 왼쪽, 위, 왼..

https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 오늘 코테에서 나온 유형과 비슷한 것 같아서 풀어봤는데,, 전혀 비슷하지 않았다 ㅎㅎㅎ 암튼, 이 문제는 거꾸로 포문을 돌면서 max값을 찾고, max 값보다 작을 경우에는 max값과의 차이(즉, 이익) 를 result에 넣어준다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamR..

https://www.acmicpc.net/problem/1515 1515번: 수 이어 쓰기 세준이는 1부터 N까지 모든 수를 차례대로 공백없이 한 줄에 다 썼다. 그리고 나서, 세준이가 저녁을 먹으러 나간 사이에 다솜이는 세준이가 쓴 수에서 마음에 드는 몇 개의 숫자를 지웠다. 세준 www.acmicpc.net 실버3으로 하루를 가볍게 시작하고자 했지만,, 실버3레벨 치고 문제 이해부터 어려웠던 문제였다.. 감을 잃은건지 ㅠㅠ 너무 슬프당.. 코테 준비는 할수록 미궁으로 가는 느낌이랄까 ㅠㅠ 아무튼! 234092 을 예시로 들자면, 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 검정색인 숫자들을 다솜이가 지운거다!! 이를 확인하기 위해서는 임의의 수 i를 생..

https://www.acmicpc.net/problem/1527 1527번: 금민수의 개수첫째 줄에 A와 B가 주어진다. A는 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. B는 A보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다.www.acmicpc.net 포문을 사용해서 String을 char로 쪼개서 비교하면 메모리 초과가 난다 ㅎㅎ,, dfs를 사용해서 0부터 시작해서 아래와 같이 하면 된다. import java.io.*; import java.util.*; public class Main { static int a, b, result = 0; public static void main(String[] args) throws IOExceptio..

https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 1) n까지의 소수를 구한다. -> 에라토스테네스의 체를 사용하여 구해야 시간초과가 나지 않는다! 2) 소수 연속 합을 확인한다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int n; public static void main(String[] args) throws NumberFormatException, IOException { Buffered..

https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 이중 포문으로 하면 되지~ 생각했다가 역시나 시간초과 였다,, ㅎㅎㅎ 투 포인터를 사용해서 해결할 수 있는 문제였다. 1. 정렬 2. 양 끝의 번호를 더해서 해당 값이 이루어지는 지 확인하고 더 작다면 앞번호+1 , 더 크다면 뒷번호-1을 하여 반복한다. import java.io.BufferedReader; import java.io.IOE..

https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 일차원배열에 이차원배열의 값들을 넣고 sort하는 방식으로 접근했더니 역시나 10억이 넘기에 메모리 초과였다,, 1. 이분탐색으로, mid을 z번째 숫자라고 생각한다. 2. 줄마다 mid보다 작은 값이 몇개 있는지 확인한다. 즉, Math.min(mid / i번째 줄 , n)의 값을 모두 더한다. 3. 모두 더한 값이 k와 같을 경우-> result는 mid 이다! ..

https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 다익스트라를 두번 쓰면 해결할 수 있는 문제이다! 단방향이래서 일방통행인줄 알았는데 계속 오류가 나서 보니, 일방통행이 아니었다..! 목적지부터 pq에 넣어서 목적지와 연결된 곳들부터 거리를 계산해나간다! import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader..

https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 1. ArrayList에 빈칸 정보를 넣는다. 2. 1~9까지 포문을 돌면서 행,열, 3*3 배열에서 해당 값으로 세팅해도 되는지 확인한다. 된다면 arr배열에 해당 값으로 세팅하고, list의 다음 빈칸으로 넘어간다. 안된다면 arr배열에 0으로 세팅하고, 다음 숫자로 넘어간다. 3. 그렇게 list의 마지막까지 세팅할 값을 찾았다면 print~~ import java.io.BufferedRea..