Jerry의 기록저장소

https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 알고리즘 스터디에서 못 풀었던 문제를 dp를 공부하고 나니 이제 풀 수 있었다! 30분 컷! 이제 dp문제를 어떻게 풀어야 할지 감은 잡을 수 있을 것 같다. 근데 실버 2인데 왜 실버 1이었던 RGB거리보다 어렵지?. 스티커를 선택하면 변을 공유하는 다른 스티커들은 사용할 수 없다고 한다. 여기서 생각한 점 왼쪽부터 시작해서 윗줄의 스티커를 선택하면 다음엔 아랫줄의 스티커를 선택하면 ..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 백준님이 코테에서 dp는 잘 안 나온다고 하셨지만 그래도 dp문제를 잘 못 푼다고 생각해서.. 쉬운 문제를 풀어보았다. 풀면서 DP의 기본은 dp[i] = dp[i-1] + a 라는 것을 알게되었다. (이전값을 통해서 현재값을 계산) 이문제의 경우에는 이전 값을 통해서 다음 값을 계산하기 때문에 굳이 리스트를 통해 dp테이블을 가지고 있을 필요는 없었다. 하지만 dp문제를 접..

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 노드의 개수가 100000개까지 이므로 인접리스트를 사용하는 것을 생각했고 루트부터 리프까지 탐색하기 위해 dfs를 사용했다. 인접리스트랑 dfs를 연습해볼 수 있었던 좋은문제! import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer; publ..

https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진 www.acmicpc.net 전형적인 dfs연습문제였다. 문제들을 bfs로 많이 풀다보니 자연스럽게 bfs로 풀려고 하는 것 같은데, 이처럼 단순한 문제는 dfs로 풀어보려는 노력을 해야겠다. 그래도 dfs 까먹거나 그런건 아니니 다행! import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; impor..

https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 깡 구현문제였는데 실버1치곤 쉽지 않았던 것 같다. 처음부터 학생 클래스를 만들어서 위치, 좋아하는 학생리스트를 넣어줬다면 탐색작업을 더 적게했을텐데.. 못생긴코드 package bj2021_06_07_상어초등학교; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; imp..