문제풀이/백준
-
[백준]10844: 쉬운 계단 수 - JAVA문제풀이/백준 2021. 2. 11. 18:51
[백준]10844: 쉬운 계단 수 www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 DP문제는 진짜진짜 많이 풀어봐야 할 것 같다. 아직 완전히 이해하고 풀 수준이 안되는 것 같다. 이 문제는 dp함수를 2차원 배열로 만들었다. dp배열 의미하는 뜻은 dp[길이][마지막 자리수가 계단이 되는 경우의 수] 이다. n이 1 일때는 다음과 같다. n이 1일때 0은 결과에 포함되지 않으므로 계산하지 않는다. dp[1][1] 1 길이가 1일이고 끝자리의 수가 1일때 앞에 올 수 있는 수는 없으므로 1이다. dp[1][2] 1 길이가 1일이고 끝자리의 수가 2일때 앞에 올 수 있..
-
[백준]2470: 두 용액 - JAVA문제풀이/백준 2021. 2. 10. 18:45
[백준]2470: 두 용액 www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 풀이 이분탐색 문제를 풀어보려고 풀었는데 풀고나니 이분탐색 문제보다는 투포인터? 라는 문제라고 한다. 배열을 정렬한 후 첫 인덱스와 마지막 인덱스 값을 증감하며 적절한 위치를 찾아주었다. scanner를 써서 풀면 시간초과가 났다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 2..
-
[백준]14503: 로봇 청소기 - JAVA문제풀이/백준 2021. 2. 10. 16:32
[백준]14503: 로봇 청소기 - JAVA www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 풀이 조건에 맞는 모든 경우를 탐색해야 하므로 dfs를 사용하여 풀었다. 여기서 중요한 조건은 탐색을 할 때에는 이전으로 되돌아 갈 수 없다는 조건이다. 예를들어서 아래와 같은 경우이고 시작 위치가 1,1일때 1 0 0 1 0 1 1 0 0 dfs로 탐색을 한 방향으로 하고 나면 아래와 같아진다. 1 2 2 1 2 1 1 0 0 이후에는 원래 dfs라면 1,1로 돌..
-
[백준]1916: 최소비용 구하기 - JAVA문제풀이/백준 2021. 2. 9. 16:08
[백준]1916: 최소비용 구하기 www.acmicpc.net/problem/1916 풀이 전형적인 다익스트라 알고리즘을 사용하는 문제였다. 채점할때 50퍼센트에서 계속 틀리길래 이것 저것 건드려 보다가 초기화 하는 값을 변경해 주었더니 맞았다. 거리를 계산하는 문제들을 풀 때에는 초기화 값을 항상 신경써서 설정해 주어야 겠다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 import java.util.*; p..
-
[백준]17406: 배열 돌리기4 - JAVA문제풀이/백준 2021. 2. 9. 15:19
[백준]17406:배열 돌리기4 www.acmicpc.net/problem/17406 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net 풀이 회전 순서에 따라 결과가 바뀌므로 순열을 사용하였다. 순열로 K의 회전 순서를 뽑은 후 회전시켰고, 회전이 끝난 후 각 배열의 행의 최솟값을 계산해주었다. 순열은 어렵지 않았지만 회전하는 부분이 생각해주어야 할 조건이 많아서 시간이 오래걸렸다. 회전을 하기 위해 한 자리씩 이동할 때 회전 방향에 존재하는 가장 마지막 값들이 지위져 이 값들을 따..