Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 1188 음식 평론가
- 원격 연결 포트 포워딩
- django
- 2961 도영이가 만든 맛있는 음식
- django 프로젝트 시작
- 2643 색종이 올려 놓기
- The requested operation has failed!
- 1188 java
- django apache deploy error
- windows 원격 연결 설정
- django windows 배포 에러
- 2961 java
- 2643 java
- apache pythonpath
- 2661 java
- APPEND_SLASH = FALSE
- django 웹 페이지
- 18233 러버덕
- 공유기 원격 설정
- java di
- 14711 java
- 14711 타일 뒤집기
- django httpd error
- django settings.py
- 18233 비트마스킹
- django The requested operation has failed!
- windows apache wsgi 에러
- Problems occurred while performing provisioning operation
- 2661 좋은 수열
- 18233 java
Archives
라이브러리는 도서관 아닌가요
백준 (BOJ) 12026 BOJ 거리 java dp 본문
https://www.acmicpc.net/problem/12026
12026번: BOJ 거리
스타트가 링크를 만나는데 필요한 에너지 양의 최솟값을 출력한다. 만약, 스타트가 링크를 만날 수 없는 경우에는 -1을 출력한다.
www.acmicpc.net
이 문제 어딘가 https://verycrazy.tistory.com/122?category=1052323랑 닮아 있는데 좀 다른 문제.
백준 (BOJ) 21317 징검다리 건너기 java dp
https://www.acmicpc.net/problem/21317 21317번: 징검다리 건너기 산삼을 얻기 위해 필요한 영재의 최소 에너지를 출력한다. www.acmicpc.net 체감상 표기된 난이도 보다 훨씬 어려웠던 문제 =,.= 가지치기가 중..
verycrazy.tistory.com
정형적인 LIS와 비슷하게 풀 수 있는데, 약간 더 응용됐다고 보면 된다.
범위에 아슬아슬하게 맞춰 초기화해 풀었는데, -1로 dp 초기화해서 푸는 게 더 정직(?)하고 문제 없다고 할 수 있다.
문제를 어느정도 숙지하고 풀기 시작한 시점부터 왜 초기화가 문제인지 감을 잡게 되는 것 같다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int lth = Integer.parseInt(br.readLine());
String str = br.readLine();
int[] dp = new int[lth];
for(int i=1; i<lth; ++i) dp[i] = 1000001; // -1 사용해서 진행하는 풀이도 있다.
for(int i=1; i<lth; ++i){ // i=0은 무조건 B
char prevShouldBe;
if(str.charAt(i) == 'B'){
prevShouldBe = 'J';
}else if(str.charAt(i) == 'O'){
prevShouldBe = 'B';
}else{ // == 'J'
prevShouldBe = 'O';
}
for(int j=0; j<i; ++j){
if(str.charAt(j) == prevShouldBe){ // -1로 초기화했을 때 여기서 -1 체크해줘야 함
int diff = i - j;
int energy = diff * diff + dp[j]; // 이전 j 위치까지 도달하는데 사용한 에너지
dp[i] = Math.min(energy, dp[i]);
}
}
}
if(dp[lth-1] == 1000001){
System.out.print(-1);
}
else{
System.out.print(dp[lth-1]);
}
}
}
'알고리즘 문제' 카테고리의 다른 글
백준 (BOJ) 10710 실크로드 java dp (0) | 2022.08.24 |
---|---|
백준 (BOJ) 7983 내일 할 거야 java 그리디 (0) | 2022.07.07 |
백준 (BOJ) 2624 동전 바꿔주기 java dp (0) | 2022.07.06 |
백준 (BOJ) 9084 동전 java dp (0) | 2022.07.05 |
백준 (BOJ) 20058 마법사 상어와 파이어스톰 bfs, 구현 (0) | 2022.06.28 |
Comments