.

문제1082번: 방 번호 (acmicpc.net)접근 방식예제의 답을 직접 구해보니 그리디로 현재 갖고 있는 금액(M)으로 구매 가능한 가장 큰 수를 맨 앞자리로 설정하고, 남은 금액으로 같은 작업을 반복해서 진행하는 식으로 구하면 될 것 같다고 생각했다.  그러나 다음 아이디어를 떠올렸다.무조건 큰 수만 많이 차지하면 안 된다. 작은 수를 택하더라도 자릿수가 커야 한다.최대로 만들 수 있는 자릿수를 먼저 구한 후, 그 자릿수 안에서 최댓값을 구하면 되지 않을까?자릿수를 최대로 만든다. -> M에서 선택한 숫자들의 가격의 합을 빼 남은 가격을 구한다. -> 남은 가격을 앞자리부터 분배하여 최대한 큰 수를 만든다.남은 가격을 앞자리부터 분배하여 최대한 큰 수를 만드는 방법을 모르겠어서 시작하기가 어려웠다...

문제1477번: 휴게소 세우기 (acmicpc.net)현재 N개의 휴게소가 세워져있을 때, M개의 휴게소를 더 세워서 휴게소가 없는 구간의 최댓값이 최소가 되게 하라. 입력:N(현재 휴게소 개수) M(추가할 휴게소 개수) L(고속도로 길이)(N개의 휴게소 현재 위치) 출력:M개의 휴게소를 짓고 난 후에 휴게소가 없는 구간의 최댓값의 최솟값 출력풀이이 문제는 매개 변수 탐색 문제이다.그래서 접근 방법이 정해져있다.(매개 변수 탐색 문제에 대해서는 글 하단의 유튜브 영상 참고) 휴게소 M개를 추가한 후에 휴게소가 없는 구간의 길이를 구해서 비교하는 방법이 아니라휴게소가 없는 구간의 길이를 먼저 정한 다음, 해당 길이일때 휴게소가 몇 개 지어질 수 있는지 확인하는 방식으로 풀어야 한다. 만약 아래와 같은 값이..

문제12904번: A와 B (acmicpc.net)1. 문자열 S, T가 주어진다.2. S를 변형하여 T가 될 수 있는지 출력한다.풀이S->T 로 변형 가능한지 확인하는 경우 :조건에 따른 모든 경우를 구해야 판단 가능하므로 2^n번의 연산이 필요하다.2^10 = 약 1,000 이므로 최악의 경우 2^1000 = 약 1000^100  T->S 가 될 수 있는지 확인하는 경우:이 경우는 문자열 T의 끝 문자가 A인 경우 A를 삭제, B인 경우 B를 삭제 후 뒤집는 경우만 연산하면 되므로 총 n번의 연산이 필요하다. 앞선 방법보다 훨씬 적은 시간복잡도로 구할 수 있다. 코드import java.util.*;import java.io.*;public class Main { public static voi..

문제2143번: 두 배열의 합 (acmicpc.net)1. 배열 A, B에 대해 각 부배열을 구한다.2. 부배열은 연속된 원소들로 이루어진 부분배열이다.3. A배열의 부배열의 합 + B배열의 부배열의 합 = T가 되는 모든 부배열 쌍의 개수를 구하라.풀이1. 배열의 부분합을 구한다.2. 부분합을 각 리스트에 넣는다.3. 두 리스트의 값을 투포인터로 선택한다.4. 합이 T가 되는 경우를 count한다. 부배열의 합을 구할 때 시간복잡도 :A, B의 원소 개수는 각각 최대 1,000개이다. 이때 배열의 모든 부배열을 구하려면 부배열의 원소가 1, 2, ..., 1,000개인 경우를 모두 구해야 하므로 시간복잡도는 배열 한 개당 O(n^2) 두 리스트에서 값을 하나씩 선택하는 경우 시간복잡도 :한 리스트에 저..

문제1759번: 암호 만들기 (acmicpc.net) 조건 :1. 암호: 서로 다른 L개의 알파벳 소문자 2. 최소 1개의 모음(a e i o u), 최소 2개의 자음 3. 알파벳이 증가하는 순서로 배열되어있음 **놓칠뻔한 조건**암호가 acb가 되면 안 된다.4. 암호로 사용하는 문자의 종류는 C가지 5. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하라 6. 사전 순으로 출력하라 입력 : 4개의 알파벳 소문자, 6개의 문자 종류 a t c i s w (6개의 문자 종류)풀이1접근 알고리즘 :입력값의 범위가 3에서 15로 작으므로 브루트포스를 사용한다.브루트포스로 모든 조합을 검사하는 과정에서 백트래킹으로 시간복잡도를 줄여준다. 처음에는 모음 1개, 자음 2개를 미리 정해놓고 남는 ..

문제4096번: 팰린드로미터 (acmicpc.net)1. 팰린드로미터 : 거꾸로 읽어도 같은 단어2. 2풀이 팰린드롬인지 확인한다. (투포인터 사용)맞으면 StringBuilder에 0을 추가아니면 1씩 더하며 계속 팰린드롬인지 확인하고, 팰린드롬이 되면 지금까지 더한 숫자를 StringBuilder에 추가try 1주의할 점은, 아래 코드와 같이 값을 처음부터 int로 받아버리면 '000121'과 같이 앞에 0이 있는 숫자를 121로 인식한다.따라서 String으로 받아야 한다. import java.io.*;import java.util.*;public class boj_4096 { public static void main(String[] args) throws IOException { ..

문제https://www.acmicpc.net/status?user_id=jeong52&problem_id=2473&from_mine=11. 산성 용액 : 1~1,000,000,000 2. 알칼리성 용액 : -1~-1,000,000,000 3. 양의 세 용액을 혼합한 용액 = 세 용액의 합 4. 세 용액을 혼합하여 특성값이 0에 가장 가깝게 만들어라. 풀이1(바로 정답을 보려면 풀이2로 넘어가기) 용액의 합이 1억을 넘으므로, int가 아닌 long을 사용해야 한다. 3-> 정렬 후 이분탐색..? 정렬 후 쓰리포인터? start, end 포인터를 배열의 양 끝에 위치하게 한다.합의 절댓값이 가장 작은 두  값을 선택한다.선택된 두 값 제외한 나머지 값들 중에서, 셋의 합의  절댓값이 작은 값을 마저 선택..

문제14890번: 경사로 (acmicpc.net)1. NxN인 지도에 적힌 높이를 보고 몇 개의 행과 열을 지나갈 수 있는지 출력2-1. 길에 속한 모든 칸의 높이가 같아야 길을 지나갈 수 있다.2-2. 길에 경사로를 놓아 길을 지나갈 수 있다.3. 경사로는 겹치면 안 된다.풀이구현 문제였다. 삼성 기출은 빡구현인가.. 푸는 데 3시간정도 걸린 것 같다. 1. 경사로를 놓는 방법경사로의 길이가 L로 주어졌을 때, 낮은 쪽 L개의 칸에 경사로를 둬야 한다. 경사로를 둘 자리가 있는지 확인해야 함탐색하는 방향 기준으로 높이 변화가 두 가지 있다.높->낮 : 오른쪽으로 L개의 칸에 경사로를 둬야 함낮->높 : 왼쪽으로 L개의 칸에 경사로를 둬야 함2. 탐색 방법0부터 N까지 한 줄의 행을 돌면서 현재 값과 다..

문제https://www.acmicpc.net/problem/201521. pc방으로 상하좌우 이동, 한 번에 1칸 이동 2. 최단경로로 움직임 3. y>x인 곳은 침수됨 4. 침수된 곳을 피해서 pc방까지 갈 수 있는 경로의 개수 5. pc방 좌표 == 집 좌표 -> 경로 1가지 입력: (H, H) 집 좌표  (N, N) pc방 좌표풀이1bfs, dfs - 시간초과 처음에는 방문 가능한 곳의 좌표를 리스트에 넣어서 리스트의 조합으로 풀려고 했다.그러나 이 방법은 최악의 경우 30*30행렬에서 좌표의 모든 조합을 구해야 하므로 연산 횟수가 1억이 넘는다. 다음으로 행렬을 완전탐색하는 경우를 생각해보았다.완전탐색은 일반적으로 O(2^N) O(N!)의 시간복잡도를 가지고 있다. 이 경우도 연산 횟수가 1억이..

문제16918번: 봄버맨 (acmicpc.net)폭탄은 3초 후 폭발 → 빈칸이 됨 (인접 4칸 포함)폭탄도 함께 파괴되어 연쇄 폭발 반응 없음N초 후 격자의 상태 출력하기풀이0초: 폭탄설치1초: -2초: 폭탄 없는 모든 칸에 폭탄 설치3초: 0초에 설치한 것 폭발4초: 폭탄 없는 모든 칸에 폭탄 설치5초: 2초에 설치한 것 폭발6초: 폭탄 없는 모든 칸에 폭탄 설치... 1. timeNow를 0부터 1초씩 증가시키면서 짝수인 경우, 홀수인 경우 나눠 진행한다.2. timeNow가 N이 되면 현재까지 진행된 상태 출력3. 폭탄이 3초 후에 터져야 하므로 같은 크기의 격자판을 하나 더 만들어 해당 좌표에 심어진 폭탄의 시간을 관리한다. 설치(plant()) : "."을 "O"로 바꾸는 작업. 심은 자리의 ..