BallPython BallPython

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 요약 : 길이가 N인 수 중, 계단수가 총 몇 개인지 구하는 문제 dp[n][i] : 길이가 n인 수에서 i가 마지막에(n번째에) 들어갈 때, 그 수가 계단수가 되는 경우의 수 처음에는 1차원 dp 배열로 풀이 하려고 했는데 길이도 따져야 하고 이전 수와의 관계도 따져야 해서 헤매다가 2차원으로 구현하게 되었다. 어렵다=__=; dp[n][i] = dp[n-1][i-1]+dp[n-1][i+1]의 의미는 다음과 같다. 길이가 n인 숫자의 제일 마지막에 i가 온 상태에서 그 수가 계단수가 되기 위해서는 바로 ..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 각 집을 빨강으로 칠할 때, 초록으로 칠할 때, 파랑으로 칠할 때 드는 비용이 주어진다. 비용은 1,000보다 작거나 같은 자연수이다. www.acmicpc.net 대표적인 DP 문제라고 한다. 문제를 한 문장으로 정의하자면 ' N개의 집을 이웃집과 색이 겹치지 않게 칠하는데 드는 최소가격'을 구하는 문제이다. dp[i][] : i 집까지의 최소 cost로 정했다. 일단 dp[i][0]은 i번째 집을 빨간색으로 하는 최소 가격이다. dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2])+cost[i]..

백준 14501번 퇴사 문제입니다. schedule 메소드에서 1)day번째 날에 상담을 하는 경우와 2)하지 않고 다음 날짜로 바로 넘어가는 두 경우에 대해서 재귀 함수를 돌려서 답을 구합니다. 주의할 점은 퇴사하고 난 날짜에 상담 일정을 잡지 않는 것입니다.일정을 잡기 전에 day+T[day]

오랜만에 알고리즘 문제를 풀어냈다...요즘 스터디에서 삼성 코테 준비하는데 너무 어려워서건드는 것마다 못 풀어내는 중이댜 엉엉ㅠㅠ하다 보면 늘겠지 싶지만서두 답답하다! 어쨌든 오늘은 경사로 문제를 풀어냈다!! 경사다~~~(덩실) https://www.acmicpc.net/problem/14890 *저는 메소드를 가로 경로로만 움직이면서 경사로 조건을 체크하도록 만들었습니다. 대신 세로 경로는 입력 받을 때 가로 경로로 변환해서 입력받았어요.map[i][j] = arr[j][i] 이렇게 입력 받았어요. 아래 사진은 map[i][j]와 arr[i][j]입니다. (사실 메소드를 좀 활용성 있게(?) 짜보고 싶었는데 머리는 머리카락 기르는 화분인 지 잘 안 돼서그냥 입력을 바꿔서 했어요^^ㅎㅎ) 1. 지도를 배..

백준 2455번 문제 풀이입니다. 4개의 역에서 내린 사람 수와 탄 사람 수가 주어졌을 때, 기차에승객이 가장 많을 때, 그 사람 수를 계산하는 프로그램입니다. 정답률도 높고 간단한 문제입니다! 1. 각 역마다 내리는 사람 수와 타는 사람 수를 입력받습니다. (변수 out, in)2. 그 역마다 승객 수를 구해줍니다. 3. max 함수를 이용해서 최대 승객 값을 max_total에 넣고 출력해줍니다. 1234567891011121314151617181920212223242526272829303132package mnth_12;import java.util.Scanner; public class BJ2455 { public static void main(String[] args) { // TODO Auto..

단지 번호 붙이기를 DFS로 풀어보았습니다.개인적으로 BFS보다 DFS가 코드가 간결하고 쉽네요. find 함수에서,주어진 좌표의 사방을 돌면서 조건에 만족하는 값에 대해서 다시 find 함수를 호출하게 됩니다.그와 동시에 cnt 값을 증가시킵니다.만약 사방을 둘러보았는데 조건에 맞는 값이 없을 때는 cnt 값을 리턴해서 ArrayList에 값을 추가합니다. 이렇게 반복해서 총 단지 수는 ArrayList의 사이즈로,단지 내의 집의 수는 ArrayList내에 저장된 값으로 출력해줍니다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566..

Queue를 이용하여 BFS로 풀었습니다! Main함수에서는,1) 단지를 입력 받습니다2) 단지 배열 값이 1이고, 이전에 방문한 적 없는 값은 BFS 함수를 호출합니다3) BFS를 호출할 때마다 count를 해서 그 값을 총 단지수로 출력해줍니다.4) ArrayList와 Collection을 이용하여 값을 오름차순으로 정렬해 각 단지 내 집의 수를 출력해줍니다. BFS함수에서는,1) 메인에서 전해준 값을 큐에 넣고, visit 체크를 합니다.2) 그 값의 주변(상하좌우)을 살피며 값이 1이고 방문한 적 없는 값을 Queue에 넣습니다.그리고 local_cnt를 증가하며 한 단지 내의 집의 개수를 카운트 합니다. 3) local_cnt를 ArrayList에 추가합니다. 풀면서 번거로웠던 점은 map을 입..

문제는 결국 입력1부터 입력2까지의 최소 거리를 구하는 것입니다. 최단 거리인 만큼 BFS로 풀어보았습니다. 1. 수빈이의 위치(조건이 3가지 존재)를 큐에 넣어가면서 이동2. 배열에 방문 여부를 체크해서 중복되지 않도록 하기3. 이동할때마다 1씩 더해서 거리체크하기 수빈이의 위치가 변하는 조건은 현재 위치-1 , 현재 위치+1, 현재 위치*2입니다. BFS에서 현재 위치가 입력2와 같으면 거리를 출력해주도록 했습니다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364package mnth_11;import java.util.Scanner;i..