본문 바로가기

전체 글111

[JAVA] 백준 20440 니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마 오늘의 문제 : https://www.acmicpc.net/problem/20440 아니 모기송하면 이광수 님의 모기송 아닌가요?나참. 처음에는 PQ를 사용하여 도전을 해봤는데 계속 실패해서 다른 분의 코드를 흡수헀습니다.  HashMap을 사용하여 특정 시간에 모기가 얼마나 들어고 나갔는지를 저장하는 방법입니다.  HashMap을 사용한 이유는 모기가 들어오고 나간 시간 사이는 탐색을 할 필요가 없어서 라고 생각합니다. 예를 들어 1,20에 모기가 들어왔다면, 그 사이 수 2,3,4,.. 19는 다 같은 모기 수를 갖고 있음으로 탐색할 필요가 없습니다.  문제에서 시간의 최대 값를 21억으로 말한 것도 힌트가 될 수 있겠습니다.  구현은 간단합니다.  코드import java.io.BufferedRea.. 2024. 10. 7.
[Java] 백준 1943 동전 분배 오늘의 문제 : https://www.acmicpc.net/problem/1943 그리디로 풀다가 실패해서 백트래킹으로 다시 도전 후 또 실패하고 정답을 맞힌 문제입니다. 1. 그리디 동전을 내림차순으로 정렬 후 현재 더 적은 금액을 가지고 있는 사람에게 동전을 주도록 하였습니다. 그럴 듯 하지만...313 13 12 8위와 같은  상황에서는 적절하지 못하게 동전을 분배합니다. (제가 직접 생각했어요 뿌듯) 2. 백트래킹 모든 경우를 전부 확인해야 한다고 생각하여, 백트래킹을 통해 확인했습니다.  하지만 테스트 케이스 3개 * 2의 n*n(대략)의 시간복잡도가 나오기 떄문에 시간을 초과하게 됩니다.  - 백트래킹 코드import java.io.BufferedReader;import java.io.IOEx.. 2024. 10. 4.
[JAVA] 백준 4933 뉴턴의 사과 문제 : https://www.acmicpc.net/problem/4933 혹시 문제를 풀기 전에 모호한 부분이 많아서 시도를 못하신 분들은 아래 글을 읽어 보고 다시 도전해 보세요! + 문제 부연 설명 "두 트리가 같다"에 대해  - '두 트리가 같다'는 부모 내 자식들의 자리를 바꿔서 같은 트리가 된다면 같은 트리입니다.  -  구조는 같지만 같은 위치의 정점 이름(A, B..) 이 다른 경우에 대해서는 과감하게 같지 않은 트리라고 생각하셔도 됩니다. 입력 범위에 대해.  - 모든 채점 결과에 대해(지금 기준)  "시간초과"가 나온 적이 없는 문제입니다. 크게 신경 쓰지 않으셔도 됩니다. 혹시 저만 모호하다고 생각했나요..? 그럼 이제 문제를 풀어보겠습니다. 문제를 정리해 보자면 입력받은 값으로 트리.. 2024. 10. 2.
[JAVA] 백준 20055 컨베이어 벨트 위의 로봇 오늘의 문제 : https://www.acmicpc.net/problem/20055 조건을 확실하게 정리하는 습관을 기릅시다. 왜 와이? 요번문제에서 바로 코딩 들어가서 삽질을 좀 했기 때문이죠. 투 포인터 및 구현문제입니다. 1. 작업의 순서    1) 벨트가 돌아간다.    로봇이 끝부분에 도달하는 즉시 벨트에서 나온다.     시작점과 끝점을 -1 시켜 벨트의 회전을 구현.   2) 로봇이 이동한다.  3) 로봇이 추가된다.    현재 추가할 경로의 내구도가 0인 경우 패스.    현재 추가할 경로에 로봇이 이미 있다면 패스.  2. 로봇의 이동 상황 구분.  1) 이동할 로봇이 이미 끝부분에 있는 경우    즉. 시 제외.  2) 이동할 로봇의 다음경로에 이미 로봇이 있는 경우    원래 위치 그.. 2024. 9. 30.
[JAVA] 백준 2151 거울 설치 오늘의 문제  :https://www.acmicpc.net/problem/2151 거울을 좋아하는 채영이를 위해 문 앞에서 다른 문이 보이도록 거울을 설치해줘야 합니다. 부자인가 봐요.  BFS 탐색을 통해 풀었습니다.  1. 입력 받은 문 하나에서 보이는 거울의 좌표를 우선순위 큐에 넣기 - 4방향으로 볼 수 있고, 만약 하나의 거울의 좌표를 발견 하더라도 탐색은 계속 진행되어야 합니다.  - 넣어준 거울의 좌표에 대해 visit[][] 값을 1로 넣어줬습니다. 이를 통해서 '거울 순환 상황' 체크 및 효율적인 탐색을 수행하였습니다.  거울 순환 상황은 예로5***** *!.!#*!.!**.!.**#*** 위 와 같은 경우 (1,1),(1,3),(2,3),(2,1)로 다시 시작 문으로 돌아오는 경우는 .. 2024. 9. 29.
[JAVA] 백준 20183 골목 대장 호석 - 효율성 2 요즘 백준 하루 1문제씩 문제를 뽑아주는 사이트가 있어서, 하루에 한 문제씩 풀고 있습니다.  한 1주일 했는데, 블로그를 써야지 써야지 하다가 지금 작성합니다.  https://www.acmicpc.net/problem/20183 아 근데 이거 링크 박스가 왜 안나올까요...고칠기력이 없는데. 풀이  문제가 뭐 말이 되게 많은데 정리하면 시작점부터 도착점까지 최소의 수치심과 최소의 비용을 가지고 가야 합니다.  위 요구사항을 가지고 조건을 정리해보자면,  - 현재 탐색 중인(Walker) 가 골목길을 통해(Edge)에 노드(Pair)에 도착했을 때, 만일 Walker의 현재 사용한 비용 + 골목길의 비용이 가지고 있는 돈보다 크다면 못 감 - Walker의 수치심과 골목길의 비용 중 더 큰 값이 현재 .. 2024. 9. 24.

티스토리툴바