본문 바로가기

Baekjoon

 (29)
[JAVA] 백준 2193번 : 이친수 [문제] [입력] 첫째 줄에 N이 주어진다. [출력] 첫째 줄에 N자리 이친수의 개수를 출력한다. [예제 입력] [풀이 과정] 정말 오랜만에 풀어보는 DP... 실버임에도 불구하고 머리가 돌아가지 않았다.. 흑흑 문제와 조건은 간단하다. 이진수가 있다. 조건 1 ) 첫째 자리는 0으로 시작하지 않는다. 조건 2 ) 1이 두 번 연속해서 나오지 않는다. 조건에 해당하는 이진수의 개수를 찾는 문제이다. 최대 N=90이기 때문에 완전 탐색으로 풀 수 없는 문제이다. (경우의 수가 엄~~~청 큼) 이 문제에서 신경써야 할 부분은 조건 2이다. 1이 연속해서 두 번 나오지 않는다는 것. 이를 잘 이용하면 간단하게 풀 수 있다. 맨 오른쪽 끝 자리에 0을 넣을지 1을 넣을지에 대해서 생각하면 된다. 예를 들자면 N..
[Java] 백준 17396 : 백도어 [문제] https://www.acmicpc.net/problem/17396 17396번: 백도어 첫 번째 줄에 분기점의 수와 분기점들을 잇는 길의 수를 의미하는 두 자연수 N과 M이 공백으로 구분되어 주어진다.(1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000) 두 번째 줄에 각 분기점이 적의 시야에 보이는 www.acmicpc.net 유섭이는 무척이나 게으르다. 오늘도 할 일을 모두 미뤄둔 채 열심히 롤을 하던 유섭이는 오늘까지 문제를 내야 한다는 사실을 깨달았다. 그러나 게임은 시작되었고 지는 걸 무척이나 싫어하는 유섭이는 어쩔 수 없이 백도어를 해 게임을 최대한 빠르게 끝내기로 결심하였다. 최대한 빨리 게임을 끝내고 문제를 출제해야 하기 때문에 유섭이는 최대한 빨리 넥서스가 있는 곳으로 ..
[Java] 백준 14938 : 서강그라운드 [문제] https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 하는 게임이다. 서강그라운드에서 1등을 하면 보상으로 치킨을 주는데, 예은이는 단 한번도 치킨을 먹을 수가 없었다. 자신이 치킨을 못 먹는 이유는 실력 때문이 아니라 아이템 운이 없어서라고 생각한 예은이는 낙하산..
[JAVA] 백준 20160번 : 야쿠르트 아줌마 야쿠르트 주세요 [문제] https://www.acmicpc.net/problem/20160 20160번: 야쿠르트 아줌마 야쿠르트 주세요 첫 줄에는 정점의 개수 V(1 ≤ V ≤ 10,000)와 도로의 개수 E(0 ≤ E ≤ 100,000)가 정수로 주어진다. 그 다음 E 줄에 걸쳐 각 도로를 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u 와 v(1 ≤ www.acmicpc.net 야쿠르트를 외치며 잠에서 깼다. 오늘은 야쿠르트로 하루를 시작하려고 한다. 야쿠르트 아줌마는 10개의 지점을 최단 시간으로 이동하며 들리신다. 각 지점에서 야쿠르트 아줌마보다 같거나 더 일찍 도착한 사람에게 야쿠르트를 팔고 바로 다음 지점으로 출발하신다. 각 지점은 정점 위에 있고 지정된 차례에만 야쿠르트를 판매한다..
[Java] 백준 1238 : 파티 [문제] https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다. 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. ..
[Java] 백준 1600: 말이 되고픈 원숭이 (2차원 배열 풀이) [문제] https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 문제 요약 : 원숭이는 출발지점에서 도착지점에 가야 하는데 인접 한 방향 (상하좌우- 8방향)로 이동하거나 문제에서 주어진 기회를 이용하여 만큼 말처럼 이동 (8방향 -체스의 나이트와 같은 이동 방식) 해서 움직여야 하는 문제. 가장 최소한의 동작 수를 구하는 문제이다. [풀이 과정] 이 문제 풀이를 검색했을 때 주로 3차원 배열을 사용한 풀이 방법이 많아서 2차원 배열로..
[Java] 백준 1034 : 램프 [문제] https://www.acmicpc.net/problem/1034 1034번: 램프 첫째 줄에 N과 M이 주어진다. N은 행의 개수이고, M은 열의 개수이다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 램프의 상태가 주어진다. 1이 켜져있는 상태이고, 0이 꺼져 www.acmicpc.net [풀이 과정] 문제 요약 : 각 열에 달려 있는 스위치를 K번 눌러서 켜져있는 행의 개수의 최대값을 구하는 문제이다. 스위치를 누르면 그 열에 있는 램프의 상태가 바뀌게 되는데 , 켜져있는 램프는 꺼지고 꺼져있는 램프는 켜진다. N과 M의 범위는 1부터 50 , K의 범위는 0 혹은 1~1000까지의 자연수이다. 처음에는 , 모든 경우를 전부 확인하기 위하여 하나의 열에 대해서 스..
[Java] 백준 1043 : 거짓말 [문제 풀이] 문제를 간단히 요약하자면 지민이는 파티에 참가하여 거짓말을 하거나 진실을 말하게 된다. 파티에 진실을 알고 있는 사람이 존재한다면 지민이는 거짓말쟁이가 되기 싫기때문에 거짓말을 칠 수 없게된다. 거짓말을 치면 거짓말 쟁이가 된다! 이때 지민이가 거짓말쟁이로 알려지지 않으면서 , 과장된 이야기를 할 수 있는 파티 개수의 최대값을 구하는 문제이다. 파티에 참여한 사람들 중 진실을 알고 있는 사람이 존재하면 지민이는 거짓말을 칠 수 없다. 따라서 진실을 아는 사람들의 집단을 만들어서 파티에 참여하는 사람들이 진실을 알고 있는 집단에 속해있는지 판단하며 정답을 구하려 한다. [1. 변수 선언 및 초기화] 인덱스 번호의 사람의 부모 인덱스를 저장하기 위해 parent[] 배열을 선언했다. paren..

티스토리툴바