본문 바로가기

백준98

백준 1003번 : 피보나치 함수 문제 www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 구현 방법 int 배열을 선언하여 0의 개수와 1의 개수를 따로 세주었습니다. N이 0일 때 0의 개수는 1, 1의 개수는 0 N이 1일 때 0의 개수는 0, 1의 개수는 1 N이 1보다 크면 i-2의 0 개수, i-1의 0 개수를 더해서 i의 0값에 저장, i-2의 1 개수, i-1의 1 개수를 더해서 i의 1값에 저장해줍니다. 구현 코드 package BOJ.Silver; import java.io.BufferedReader; import java.io.IOException; import java... 2021. 3. 19.
백준 2210번 : 숫자판 점프 www.acmicpc.net/problem/2210 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net 구현 방법 가능한 모든 곳을 탐색해야 하기 때문에 브루트포스 알고리즘을 사용해주었습니다. 깊이를 따라 가야하기 때문에 dfs를 통해 탐색을 진행하였습니다. 한 번 거쳤던 칸은 다시 거쳐도 되므로 방문체크는 따로 하지않고 카운팅을 해주어 다섯 곳을 이동했으면 중복을 허용하지 않는 TreeSet을 구현하여 해당 문자를 삽입해주었습니다. 다섯번을 이동했으면 더 이상의 탐색을.. 2021. 3. 18.
백준 2583번 : 영역 구하기 문제 www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 구현 방법 해당되는 영역들을 1로 채운 다음 빈 칸을 중심으로 dfs를 통해 구현하였습니다. 한 영역에서 탐색이 끝난 후 계산한 너비를 저장을 합니다. 모든 영역 탐색이 끝난 뒤에 저장해 둔 너비들을 정렬 하고 출력해줍니다. 구현 코드 package BOJ.Silver.bfsdfs; import java.io.BufferedReader; import java.io.IOException;.. 2021. 3. 18.
백준 1937번 : 욕심쟁이 판다 문제 www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 구현 방법 그냥 bfs/dfs를 쓰면 시간 초과가 나기 때문에 dp를 써줘야합니다. 예제를 예로 들면 9->11->15 방향으로 탐색을 합니다. 나중에 5->11로 갈때면 11은 15까지밖에 못간다는걸 이미 알고있는데 탐색을 하므로 시간이 낭비됩니다. 그래서 자기가 이미 갔던 곳이라면 살 수 있는 날을 저장을 하고 그 곳을 또 방문하게 된다면 저장되어 있는 값을 가져와 +1을 해주면 자신의 살 수.. 2021. 3. 18.

티스토리툴바