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

www.acmicpc.net/problem/2571 2571번: 색종이 - 3 첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변 www.acmicpc.net 문제 : 색종이를 여러개 겹쳐서 가장 큰 직사각형의 넓이를 구해라 해설 : 직사각형은 전부 선분이 일직선이여야 되니 될수 있는 경우의 수를 다 해주었다. 판의 최대 크기는 100이니 직사각형의 가로/세로의 길이를 1부터 시작해서 100까지 늘려주면서 해당하는 직사각형을 그릴 수 있는지 판별해 주었다. #include using namespace std; int board[101][101], v[101][101]; ..

www.acmicpc.net/problem/2688 2688번: 줄어들지 않아 첫째 줄에 테스트 케이스의 개수 T(1 t; memset(dp, -1, sizeof(dp)); for (int i = 0; i > n; for (int j = 0; j < 10; j++) sum += dp[n][j]; cout

www.acmicpc.net/problem/3495 3495번: 아스키 도형 창영이는 메모장에 '.', '\', '/'을 이용해서 도형을 그렸다. 각 문자는 그림에서 1*1크기의 단위 정사각형을 나타낸다. '.'은 빈 칸을 나타내며, '/'는 정사각형의 왼쪽 아래 꼭짓점과 오른쪽 위 꼭짓 www.acmicpc.net 문제 : 그냥 문제에 나와있는 도형의 넓이를 구해라 해설 : '/' 이나 '\' 은 1/2 의 넓이를 갖는 것이 분명하고 , 문제는 '.' 일때 도형 안과 밖을 구분하여 넓이에 더해주어야 된다. 이를 필자는 처음 잘못 생각해서 상하좌우 쭉 갔을때 '/' 이나 '\' 이 존재하면 count 해서 구분해줄려고 했는데 도형안에 존재하지 않아도 상하좌우에 도형이 감쌓고 있는 경우가 있을 수가 있게 ..

www.acmicpc.net/problem/20167 20167번: 꿈틀꿈틀 호석 애벌레 - 기능성 꿈틀꿈틀 호석 애벌레는 N 개의 먹이가 일렬로 나열된 나뭇가지를 오른쪽으로 기어가려고 한다. 시작하는 순간의 호석 애벌레가 0의 위치에 있고 i 번째 먹이는 오른쪽으로 i 초 기어가야 도달할 www.acmicpc.net 문제 : 애벌래는 연속적으로 먹이를 먹을 수 있음. 먹은 먹이들의 합이 k 이상일때 k를 초과한 부분을 축적함. 그리고 다시 0부터 시작. 이때 축적된 양이 최대값이 되게끔 구해라. 해설 : n의 범위가 20밖에 안되는걸 보면 모든 경우의 수를 해도 2^20 이니 충분하죠. 그래서 재귀로 싹다 돌렸습니다. #include using namespace std; int n, k,ans=0; i..

www.acmicpc.net/problem/2666 2666번: 벽장문의 이동 첫 번째 줄에 벽장의 개수를 나타내는 3보다 크고 20보다 작거나 같은 하나의 정수, 두 번째 줄에 초기에 열려있는 두 개의 벽장을 나타내는 두 개의 정수, 그리고 세 번째 줄에는 사용할 벽장들 www.acmicpc.net 문제 : n개의 벽이 주어지고 단2개만 빼고 전부 벽장문이 존재합니다. 이 벽장문을 한칸씩 양옆중 한방향으로 밀어 원하는 인덱스의 벽에 접근하면 됩니다. 이때 벽장문의 이동의 최소값을 구하는게 문제입니다. 해설: 먼저 어떻게 문제에 접근할까 부터 생각을 해보았습니다. 벽을 차례대로 사용할 번호를 배열에 담고 순차적으로 접근해야 함을 첫번째로 고려하였습니다. 그러면 사용하고자 하는 벽장과 가장 가까이에 벽장문..

www.acmicpc.net/problem/20292 20292번: 컨설팅 입력으로 최대 $10\ 000$줄의 명령어가 주어지며, WRITE문, READ문, EXIT문으로 구성된다. EXIT문은 마지막에 한 번만 주어진다. 각 명령어는 다음과 같이 정의되며, 메모리 이름은 $1$–$3$글자의 알파벳 www.acmicpc.net 문제 : 지문에 써저있는 조건에 맞게 wait를 추가하여 출력하게끔 해라. 해설 : 최대 입력 문장이 10000 인 걸 고려해서 O(n^2)은 불안하여 O(nlogn) 의 시간 복잡도를 이용하여 문제를 해결하였습니다. 더불어 C++ 언어를 사용하시는 분께선 반드시 fastio를 사용해주세요. (요즘엔 선택이 아닌 필수라고 하더라구요) 소스: #include using namespa..

www.acmicpc.net/problem/2459 2459번: 철사 자르기 가로 줄과 세로 줄의 개수가 각각 N인 바둑판 모양이 있다. 여기에서 인접한 두 가로줄 또는 두 세로줄 사이의 거리는 1이다. 또한, 가로줄과 세로줄이 만나서 생기는 교차점은 왼쪽에서 x번째 세 www.acmicpc.net 문제 : 철사를 판에 맞게 따라서 쭉 놓는다. 이때 격자에서만 꺾을 수 있다.(꺽기는 격자의 좌표는 순차적이다). 철사를 자를 l 이 주어지고 l 과 l+1 사이를 자른다. 최대의 길이를 가진 철사를 구해라 풀이 : 철사가 잘리는 좌표만 잘 처리하여 하나씩 저장해 주자. x n >> k; v.resize(k + 2); for (ll i = 1; i > v[i].first >> v[i].second; cin >..

www.acmicpc.net/problem/2651 2651번: 자동차경주대회 전국 자동차 경주 대회가 매년 열리고 있다. 이 대회에서는 출발지점부터 도착지점까지 거리가 워낙 멀기 때문에 경주 도중에 각 자동차는 정비소를 방문하여 정비를 받아야 한다. 정비소들은 www.acmicpc.net 문제 : 도착지점까지 정비소에 들려 최소의 시간으로 도착할 수 있는 케이스를 구해라 풀이 : LIS의 응용버전 1)각 정비소간 거리를 prefix 로 담아준다. 2)O(n^2)의 시간복잡도를 활용하여 정비소간 차이가 D(정비소에 들렸을때 최대로 갈 수 있는 거리) 이하이고 시간이 더 적게 걸릴때 업데이트, 또한 지금까지 거쳐온 정비소의 번호를 기록해 둔다. 3)지나온 자취를 역추적 + 데이터 추가로 코드 수정(int-..

www.acmicpc.net/problem/2020 2020번: 부분 염기서열 길이 n(1≤n≤1,000)인 염기서열이 있다. 이는 A, G, C, T로 구성되어 있는 문자열이라 생각할 수 있다. 주어진 염기서열의 부분 염기서열은, 염기서열을 문자열로 생각했을 때 부분문자열과 같이 정 www.acmicpc.net 문제 : 문자열이 주어지고 동일한 부분 문자열의 빈도가 m 이상일때 조건에 맞게 정렬해라. 그리고 k 번째 문자열을 출력해라. 해설: 너무 어려움,,,혼자 힘으로 못풀었습니다.(메모리 제한 때문에 ㅠㅠ) 해결 과정은 BFS를 푸는 것 처럼 풀 수 있습니다. 1)입력 문자열(str)의 각 문자를 동일한 문자끼리 모읍니다.(map) 2)그리고 나서 큐를 선언하고 vector를 push 해줍니다. 3..

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섬 ..