https://www.acmicpc.net/problem/21943 21943번: 연산 최대로 $N$개의 양의 정수 $X_{i}$와 곱하기 연산자, 더하기 연산자가 총 $N - 1$개가 존재하고 괄호는 무수히 많이 사용해도 된다. 이 연산에는 곱하기 연산자와 더하기 연산자의 우선순위가 동일하다. www.acmicpc.net 풀이방법 1. 숫자의 배치를 결정한다. (perm 사용) 2. 더하기의 배치를 결정한다. (combi 사용) 3. 계산한다. (더하기 먼저 다 계산 후, 곱하기 계산) 계산 방식(좀 복잡.. 이렇게 안하는 방법이 분명 있을 것이다..) 더보기 0. 초기상태 숫자배열, 더하기배열, 곱할목록 리스트 1. 더하기인 경우 : 더한값을 각각의 배열 위치에 저장한다. 2. 더하기인데 다음연산이 ..
https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 풀이방법 중량 제한인 C 의 범위가 커서 (1
https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 풀이방법 1. 해시맵을 사용해서(Key : 이름, Value : 인덱스) 처음 들어온 이름일 경우에는 해시맵에 넣고 인덱스를 증가한다. 2. 유니온 파인드 진행 소스코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.HashMap; import..
https://www.acmicpc.net/problem/20543 20543번: 폭탄 던지는 태영이 시험을 망친 태영이가 인하대학교에 폭탄을 던진다! 인하대학교는 N×N 크기의 정사각형 모양의 땅이다. 인하대학교의 모든 땅은 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c) www.acmicpc.net 풀이방법 식을 세워서 접근한다. M = 5일 때 예시 1. (i,j의 값을 구하고자 할 때 A 위치의 값을 확인해야 한다. 2. A 블럭을 기준으로 (i-1, j) , (i, j-1), (i-1, j-1) 블럭도 그려본다. 3. 영역을 색칠하고 영역별로 이름을 매겨 두겠다(b1 ~ b9) 4. A~D 블럭의 식을 세워 본다. 우리가 여기서 구하고 싶은 것은 (i, j)의 값인 b9 블..
https://www.acmicpc.net/problem/20210 20210번: 파일 탐색기 첫 줄에 문자열의 개수 N(2 ≤ N ≤ 10,000)이 주어진다. 그 다음 N줄에 정렬할 문자열이 한 줄에 하나씩 주어진다. 모든 문자열의 길이는 100 이하이며, 알파벳 대소문자와 숫자로만 이루어져 있다. www.acmicpc.net 풀이방법 1. 문자열을 받고 Array.sort 를 변형시킨다. 2. 먼저, 문자열의 길이 중 더 큰 것만큼 for문을 돌리면서 앞 문자or숫자 를 비교한다. FO, FOO 같이 같다가 한쪽의 비교대상이 사라지는 경우 처리를 해준다. (문자열의 길이 min 값보다 i가 큰경우) 3. 문자를 앞부터 차례대로 비교한다. 경우가 3가지(숫자vs숫자, 숫자vs문자, 문자vs문자) 4...
https://www.acmicpc.net/problem/3687 3687번: 성냥개비 각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다. www.acmicpc.net 풀이방법 1. maxNum, minNum 배열로 성냥개비 수로 만들수 있는 수의 최대, 최소 값을 저장 해 둔다. ex) 성냥개비 5개로 만들 수 있는 최대 값은 5이고 최소값은 2이다. => maxNum[5] =5, minNum[5] = 2 2. 최대 값 2-1. 3개까지 만들 수 있는 수는 고정이기 때문에 max[2] = 1, max[3] = 7 을 초기값으로 두고 4부터 100까지 탐색한다.(n의 ..
https://www.acmicpc.net/problem/1949 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, www.acmicpc.net 풀이방법 1. 리스트를 생성해 연결 정보를 담는다. 2. dp[N+1][2] 배열을 생성한다. => dp[N][0] : N번째 마을이 우수마을이 아닌 경우, dp[N][1] : N번째 마을이 우수마을인 경우 3. dfs를 진행한다. => dp[N][0] : 이전마을 포함된경우 , 안된경우 중 큰 값 => dp[N][1] : 이전마을 포함 안된 경우 dfs 진행 경로 (문제에 있는 테스트케..
https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 풀이방법 1. visited[][] == 0 이라면 index를 가지고 탐색 진행 2. index 를 이용해서 사이클을 체크한다. (탐색 중 같은 인덱스를 가지고 있다면 count++) 3. 다른 index를 만난다면, 다른 사이클에 합류 되는 것 //example 3 4 DLLL DRUU RRRU 소스코드 import java.io.BufferedReader;..
