순간을 성실히, 화려함보단 꾸준함을

https://www.acmicpc.net/problem/12755 12755번: 수면 장애 수면 장애를 가진 강민이는 잠이 오지 않아 적잖은 고통을 느끼고 있다. 강민이는 잠이 오지 않을 때마다 속으로 양을 세고 있었는데, 오늘따라 백만 마리까지 세었는데도 잠이 오지 않았다. 한 www.acmicpc.net 개인적으로 너무 힘들게 풀었던 문제입니다. 이걸 대체 어떻게 푸나,,,,싶었는데 풀었네요. 1. 입력된 input(=n) 값을 가지고 증가하는 수의 자릿수를 매번 빼준다면 결국에는 1억번의 연산 밑이 될거라는 생각으로 문제를 접근하였습니다. 2. 수를 1씩 증가시켜 주면서 이 수가 몇자리수(ret) 인지 계산을 해줍니다. 3. n 값에서 ret 값을 매번 빼줍니다. 4. n 이 0이 거나 0보다 작..

[문제] : https://www.acmicpc.net/problem/8012 8012번: 한동이는 영업사원! 문제 한동이는 경상도내를 돌아다니면서 열심히 일하는 영업사원이다. 예전에는 자기가 원하는 도시만 골라서 다닐 수 있었지만 시대가 바뀌어서 이제 그렇게는 하지 못하게 되었다. 시대가 바뀜에 따라, 한동이는 회사에서 돌아야 할 도시의 목록을 받고, 그 목록대로 도시를 여행한다. 회사에서 주는 여행지 목록은 정말 안타깝게도 최적화되어 있지가 않다. 여행을 떠나기 전에 한동이는 모든 도시를 방문하는데 걸리는 최소의 시간을 알고싶어하는데, 한동이는 경영학과라 컴퓨 www.acmicpc.net [분류] : LCA 알고리즘 [조건]: 가장 핵심적이고 중요한 조건은 "도로끼리 사이클을 만들지 않는다."입니다...

[문제] : 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번 섬 사이에 중량제한이 C인 다리가 존재한다는 의미이다. 서로 같은 두 도시 사이에 여러 개의 다리가 있을 수도 있으며, 모든 다리는 양방향이다. 마지막 줄에는 공장이 위치해 있는 섬의 번호를 나타내는 서로 다른 두 정수가 주어진다. 공장이 있는 www.acmicpc.net [조건] : N개의 섬과 M개의 다리가 주어지며 각 다리에는 물품의 무게를 최대로 버틸수 있는 중량제한 W가 주어집니다.A섬 ..

[문제] : https://www.acmicpc.net/problem/16434 16434번: 드래곤 앤 던전 첫 번째 줄에 방의 개수 N (1 ≤ N ≤ 123,456) 과 용사의 초기 공격력 HATK (1 ≤ HATK ≤ 1,000,000) 가 주어집니다. i+1번째 줄엔 i번째 방의 정보를 나타내는 세개의 정수 ti, ai, hi (ti ∈ {1, 2}, 1 ≤ ai, hi ≤ 1,000,000) 가 주어집니다. ti가 1인 경우 공격력이 ai이고 생명력이 hi인 몬스터가 있음을 나타내고, ti가 2인 경우 용사의 공격력 HATK를 ai만큼 증가시켜주 www.acmicpc.net [분류] :이분탐색(파라메트릭) [조건] : 1)용사의 공격력(atk)이 주어진다. 2)N만큼의 방이 존재하며 a가 1일..

[문제] : https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다. 입력으로 주어지는 모든 수는 정수이다. www.acmicpc.net [분류] : 다이나믹 프로그래밍(DP) [구현 방법] : 유명하고(well known) dp문제를 두고 보면 빠지지 않고 나오는 문제 입니다. 흔히 "냅섹(knapsack)"문제라고 불립니다. 물건 하나씩 더해가면서 현재 가방의 무게가 w 일때 최대로 담을 수 있는 가..

[문제]:https://www.acmicpc.net/problem/16932 16932번: 모양 만들기 N×M인 배열에서 모양을 찾으려고 한다. 배열의 각 칸에는 0과 1 중의 하나가 들어있다. 두 칸이 서로 변을 공유할때, 두 칸을 인접하다고 한다. 1이 들어 있는 인접한 칸끼리 연결했을 때, 각각의 연결 요소를 모양이라고 부르자. 모양의 크기는 모양에 포함되어 있는 1의 개수이다. 배열의 칸 하나에 들어있는 수를 변경해서 만들 수 있는 모양의 최대 크기를 구해보자. www.acmicpc.net #2021/02/05 코드와 로직 수정 [분류] : 탐색(DFS) [조건]: 0으로 채워진 칸을 1로 바꾸었을때 연속적으로 존재하는 1의 개수가 가장 최대임을 찾으면 됩니다. [과정] : 1)먼저 연속적으로 붙..

[문제] : https://www.acmicpc.net/problem/2615 2615번: 오목 오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호가 붙고 세로줄은 왼쪽에서부터 오른쪽으로 1번, 2번, ... 19번의 번호가 붙는다. 위의 그림에서와 같이 같은 색의 바둑알이 연속적으로 다섯 알을 놓이면 그 색이 이기게 된다. 여기서 연속적이란 가로, 세로 또는 대각선 방향 모두를 뜻한다. 즉, 위의 그림 www.acmicpc.net [분류] : 구현 [조건] : 6개가 연속으로 존재하면 안된다.그 외에는 특별히 주의할게 없어 보입니다. [구현과정]: 너무 화..

[문제] : https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net [분류] : 다이나믹 프로그래밍(DP),브루트 포스(Brute force) 조건 : 각 상담일 마다 걸리는 기간이 정해져 있으며 남은 날짜(n) 을 넘어가서는 안된다. 금액이 최대가 되어야 한다. 과정: 처음 0번 index 부터 남은 날짜(n)을 초과 하지 않는 범위 내에서 dfs를 통해 금액의 합(ans)를 구한다. 구현 방법: 유명하고(well known) 기초적인 브루트 포스 문제입니다. 이차원 배열을 사용해 dfs를 이용하였습니다. 일일이 구해보자라는 생각이 들고 재귀 탐색을 이용하여 모든 경우의 수를 구하면 해..

[문제] : https://www.acmicpc.net/problem/9207 9207번: 페그 솔리테어 문제 페그 솔리테어는 구멍이 뚤려있는 이차원 게임판에서 하는 게임이다. 각 구멍에는 핀을 하나 꽂을 수 있다. 핀은 수평, 수직 방향으로 인접한 핀을 뛰어넘어서 그 핀의 다음 칸으로 이동하는 것만 허용된다. 인접한 핀의 다음 칸은 비어있어야 하고 그 인접한 핀은 제거된다. 현재 게임판에 꽂혀있는 핀의 상태가 주어진다. 이때, 핀을 적절히 움직여서 게임판에 남아있는 핀의 개수를 최소로 하려고 한다. 또, 그렇게 남기기 위해 필요한 최소 이동횟수를 구하는 프 www.acmicpc.net [분류]:백트래킹,브루트 포스 조건 : 수평,수직 방향으로 인접한 핀이 존재해야 하며,인접한 핀의 다음 칸은 비어 있어..