네발로 코딩하는 포메라니안

1. 문제 https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 2. 풀이과정 문제 자체를 바로 이해하기 어려웠다. 2단계에서 "파이어볼이 여러 개 있으면, 그 자리에서 나눠지고 이동은 다음 단계에 한다."는 식으로 수정했으면 좋겠다. 실행 과정 1) Node라는 클래스를 만들어 한 곳에 파이어볼이 여러 개오면, 값을 누적시킨다. 2) 다음 이동에서 cnt>1이면, 방향에 따라 이동시킨다. *남은 파이어볼의 질..

1. 문제 https://www.acmicpc.net/problem/13168 13168번: 내일로 여행 첫 번째 줄에는 한국에 있는 도시의 수 N(1 ≤ N ≤ 100)과 1인당 내일로 티켓의 가격 R(1 ≤ R ≤ 1,000,000)이 주어집니다. 두 번째 줄에는 N개의 도시의 이름이 주어집니다. 도시의 이름은 알파벳 대소 www.acmicpc.net 2. 풀이과정 간단하게 말해서, 티켓 없을 때 & 티켓 샀을 때 각각 플로이드 와샬 알고리즘으로 각 도시에서 도시까지의 최단거리를 구하는 문제이다. 하지만, 문제를 제대로 읽지 않아 테스트케이스에 없던 Taxi와 Airplane을 고려해주지 않고 NullPointer Error로 고생했다. 이 문제에서 주의 깊게 볼 점 2가지 1) 비용의 최솟값이 1이..

1. 문제 https://www.acmicpc.net/problem/1414 1414번: 불우이웃돕기 첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없음을 의미한다. 그 외의 경우는 랜선 www.acmicpc.net 2. 풀이과정 요약하면 '그래프 Minimum Spanning Tree + 연결 있는 곳만 보기' 문제이다. 1) 입력을 받으면서 전체 선의 길이를 구해놓는다. 2) 자기 자신으로 가는 선, 연결 없는 선을 거르기 & i => j와 j => i 중 더 작은 값만 넣기 3) n개의 컴퓨터가 연결될 때까지 Kruskal 실행 import java.io.*; import java.uti..

1. 문제 https://www.acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 2. 풀이과정 '관계 = 나보다 뒤에 있다'라고 정의하고 보았다. i => k 이고 k =>j이면 i=>j인 것을 모든 수에 대해 적용시키면 된다. 여기서 i==j일 때는 시작지와 도착지가 같으면 의미가 없으므로 넘긴다. 또, j를 들어가기 전 i=>k부터 성립이 안 되면 앞에서 걸러주면 시간이 단축된다. import java.io.*; import java.util.*; pub..

1. 문제 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 2. 풀이과정 입력이 아래와 같이 주어진다고 하면, 6 2 3 1 5 5 2 1 앞에서부터 증가하는 수열을 찾으면서, 그 때마다 마지막에 위치한 수도 같이 저장한다. 감소하는 수열은 뒤에서부터 증가하는 수열과 같은 의미로, 앞의 과정을 인덱스 N-1에서부터 똑같이 해주면 된다. 그리고나서, 두 부분으로 잘라서 앞부분의 제일 긴 증가하는 수열 길이 + 뒷부분의 제일 긴 감소하는 수열의 길이를 더한 값의 최대..

1. 문제 https://www.acmicpc.net/problem/5577 5577번: RBY팡! 세로로 N개의 공이 붙어있으며, 각 공의 색은 R(빨강), B(파랑), Y(노랑) 중 하나이다. 플레이어는 한 공의 색을 다른 색으로 바꿀 수 있다. 이러한 변환을 거쳐 동일한 색의 공이 4개 이상 연속되면 www.acmicpc.net 2. 풀이과정 1. 입력을 받으면서 같은 수 끼리 이어진 개수를 2차원 배열 (값, 개수)로 기록한다. ex) 1113221 => {{1, 3}, {3, 1}, {2, 2}, {1, 1}} 2. 개수를 센 배열을 순차적으로 접근하면서 simulation을 한다. 최소로 하기 위해서는 같은 색이 이어진 곳 중간을 굳이 다른 색으로 바꿀 필요가 없다. 따라서, 지금 접근한 공의..

1. 문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 2. 풀이과정 간단한 BFS문제지만, 주의해야 할 점은 현재 칸과 다음 칸이 이어져있는지 확인해야 한다는 점이다. 처음엔 터널만 있으면 간다 생각하고 풀었다가 문제를 다시 읽고 수정했다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Qu..

1. 문제 https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 2. 풀이과정 1. 팀 나누기(조합) 조합의 특성을 이용하자면, 아래 문제에서 nC1과 nC(n-1)은 같은 경우라고 볼 수 있다. 따라서 n/2개까지만 뽑는 조합을 작성하여 simulation을 돌린다. 왜 같은 경우인지 설명하자면, 두 팀으로 나누어 두 팀의 값 차이를 결과로 내기 때문에, 각 팀이 빨간팀인지 파란팀인지는 상관없다. 빨간팀의 값이 1이고 파란팀이 3일 때와 빨간팀의 값이 3이고 파란팀이 ..

1. 문제 https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 2. 풀이과정 작은 수부터 순열 생성하면서 simulation한다. [simulation 단계] 1. 해당 칸에 번호 i를 놓을 수 있는지 확인 => 못 놓으면 다음 i보고, 놓을 수 있으면 다음 단계로 2. 해당 칸에 번호를 놓고, 방문 체크 3. 다음 칸을 보자 4. 다음 칸들을 다 본 후엔, 2번 과정을 복구 import java.io.BufferedReader; import..

1. 문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4suNtaXFEDFAUf SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 2. 풀이 과정 테두리에 있지 않는 각 프로세서마다 4방향 or 선택X 경우 합쳐 5가지 경우의 수가 있다. 기본적인 부분집합인 선택O or 선택X에서 선택지가 5개로 늘어났다고 볼 수 있는 것이다. 이 문제의 핵심은 부분집합과, 재귀에서의 복구하는 과정이다. 아래 코드에서는 연결한 부분을 2로 표시한 후, 재귀가 끝나고 다시 0으로 되돌려주고 다음 case를 진행하도록 했다. impor..