BOJ

[Java/자바 백준 4485] 녹색 옷 입은 애가 젤다지?

풀이 최단 경로를 묻는 bfs 문제입니다 map에는 루피값을 넣어주고 check에 해당 경로까지 최솟값을 갱신해주면서 bfs를 풀었습니다. 아래처럼 방문한 적이 있든 없든, check에 해당 경로까지 최솟 값이 있으므로 조건을 줘서 다음경로까지의 거리합 > 현재 경로까지의 거리합 + 다음 경로 거리값 이면 큐에 넣어줬습니다. if(check[nx][ny]>check[x][y]+map[nx][ny]) { check[nx][ny]=check[x][y]+map[nx][ny]; queue.offer(new int[] {nx,ny}); } import java.io.*; import java.util.*; // bfs문제 check 현재 위치를 도달할 수 있는 최솟값을 갱신하면서 탐색 public class Ma..

[JAVA/자바 백준 1149] RGB거리

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 1. 2차원 배열 Cost에 우선 해당하는 rgb에 비용 값을 모두 넣어줍니당. 2. Cost[i][0](red) 일 경우 Cost[i][1](green) Cost[i][2](blue) 중 최솟값을 더해줍니다. 0(Red) 1(Green) 2(Blue) Cost[0][0] Cost[0][1] Cost[0][2] Cost[1][0] += Min(Cost[0][1],Cost..

[Python/파이썬 11724 백준] 연결 요소의 개수

www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 풀이 처음에 연결요소를 몰라서 구글링한 결과 그냥 이어진 덩어리를 말하는거 였네요. 간선으로 이어졌으면 한 덩어리입니다. 그래서 이 문제는 dfs나 bfs로 0~n 점까지 bfs를 써서 이어진 모든 점들을 구해주고 방문한 점은 check를 True로 하여 몇번 bfs 돌렸는지 갯수를 셌습니다! # 연결 요소의 개수 import sys from col..

[Python/파이썬 6588 백준] 골드바흐의 추측

www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 문제 짝수 n n= a+b 식에서 a 와 b 둘다 소수인 경우를 출력하라 입니다. 출력 못하는 상황이 나오면 Goldbach's conjecture is wrong. 출력하고 0누르면 exit 입력 입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다. 테스트 케이스의 개수는 100,000개를 넘지 않는다. 각 테스트 케이스는 짝수 정수 n 하나로 이루어져 있다. (6 ≤ n ≤ 1..

[Python/파이썬 14890 백준] 경사로

www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 경사로 성공분류 시간 제한메모리 제한제출정답맞은 사람정답 비율 2 초 512 MB 15148 7937 5646 54.075% 문제 크기가 N×N인 지도가 있다. 지도의 각 칸에는 그 곳의 높이가 적혀져 있다. 오늘은 이 지도에서 지나갈 수 있는 길이 몇 개 있는지 알아보려고 한다. 길이란 한 행 또는 한 열 전부를 나타내며, 한쪽 끝에서 다른쪽 끝까지 지나가는 것이다. 다음과 같은 N=6인 경우 지도를 살펴보자. 이때, 길은 총 2N..

[Python/파이썬 9465 백준] 스티커 (다이나믹 프로그래밍)

www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다...