https://www.acmicpc.net/problem/1748 1748번: 수 이어 쓰기 1 첫째 줄에 N(1≤N≤100,000,000)이 주어진다. www.acmicpc.net 문제 접근 방법 새로운 수의 자릿수 = 1부터 N까지의 전체 자릿수를 더한것과 같다. 1부터 N까지 1의자리 갯수 + 10의자리 갯수 + 100의 자리 갯수 + ... + 10의 n승 자리 갯수들을 더한다. 아래는 코드입니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int N, ans = 0 ,count =..
https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다. 또, 미로 밖으 www.acmicpc.net 문제 접근 방법 원점으로부터 이동 할 수 있는 위치를 파악한다(우측, 우측 대각선 아래, 아래) 3가지 방향이다. 이동되는 점의 기준..
https://www.acmicpc.net/problem/6064 6064번: 카잉 달력 문제 최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M과 N보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 와 같은 형식으로 표현하였다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 로 표현하고, 두 번째 해를 로 표현하였다. 의 다음 해를 표현한 것을 이라고 하자. 만일 www.acmicpc.net 문제 접근 방식 x나 y를 1씩 증가시키는 방식으로 진행 시 시간초과를 초래할 수 있다. x를 고정 시키고 출력 해를 M만큼 증가시키는 방식으로 해를 구한..
https://www.acmicpc.net/problem/1890 1890번: 점프 문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 www.acmicpc.net 문제 접근 방식 최초 지점으로 부터 오른쪽 혹은 아래로 이동을 할 수 있다. 도착 지점의 입장에서 생각해보면 왼쪽에서 도착 지점으로 오거나 위..
https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 주어진 범위의 맵 내부에서 목적지까지 도달하는 최단거리를 구하는 문제입니다. 아래는 코드입니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53..
https://www.acmicpc.net/problem/3184 3184번: 양 문제 미키의 뒷마당에는 특정 수의 양이 있다. 그가 푹 잠든 사이에 배고픈 늑대는 마당에 들어와 양을 공격했다. 마당은 행과 열로 이루어진 직사각형 모양이다. 글자 '.' (점)은 빈 필드를 의미하며, 글자 '#'는 울타리를, 'o'는 양, 'v'는 늑대를 의미한다. 한 칸에서 수평, 수직만으로 이동하며 울타리를 지나지 않고 다른 칸으로 이동할 수 있다면, 두 칸은 같은 영역 안에 속해 있다고 한다. 마당에서 "탈출"할 수 있는 칸은 어떤 영역에도 속하지 www.acmicpc.net 주어진 범위 안에 있는 각각의 울타리 내부의 양과 늑대의 수를 파악하여 조건에 따라 최종 양과 늑대 수를 출력하는 문제입니다. 아래는 코드입니..
https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다. www.acmicpc.net 원하는 채널로 이동하기 위한 최소 버튼을 구하는 문제입니다. 최초 채널이 100이라는 점을 잊지 말아야 합니다. 항상 같은 자리수가 최단 거리가 아닐 수 있다는 것도 가정해야합니다. 이동하고 싶은 채널 999 고장난 버튼 수 7개 고장난 버튼 2,3,4,5,6,7,9 이런 경우 888에서 999로 이동하는 것 보다 1000에..
항목 43 : 템플릿으로 만들어진 기본 클래스 안의 이름에 접근하는 방법을 알아 두자 1 2 3 4 5 6 template class MsgSender{ public : ... void sendSecret(const MsgInfo& info){...} }; Colored by Color Scripter 괄호 안에 아무것도 없는 template의 뜻은 "이건 템플릿도 아니고 클래스도 아니다"라는 것입니다. 위의 코드는 MsgSender 템플릿을 템플릿 매개변수가 CompanyZ일 때 쓸 수 있도록 특수화한 버전입니다. 이러한 특수화는 완전 템플릿 특수화라고 합니다. MsgSender 템플릿이 CompanyZ 타입에 대해 특수화되었고, 이때 이 템플릿의 매개변수들이 하나도 빠짐없이 구체적인 타입으로 정해진 ..
항목 42 : typename의 두 가지 의미를 제대로 파악하자 1 2 3 4 5 6 7 8 9 10 11 12 template void print2nd(const C& container) { if(container.size() >= 2) { C::const_iterator iter(container.begin()); ++iter; int value = *iter; std::cout = 2) { typename C::const_iterator iter(container.begin()); ... } } Colored by Color Scripter 어느 때이든지 템플릿 안에서 중첩 의존 이름을 참조할 경우에는, 그 이름 앞에 typename 키워드를 붙여 주는 것을 잊지 마세요. "typename은 중첩 ..
항목 41 : 템플릿 프로그래밍의 천릿길도 암시적 인터페이스와 컴파일 타임 다형성부터 객체 지향 프로그래밍의 세계를 회전시키는 축은 명시적 인터페이스와 런타임 다형성입니다. 예를 들어 아래와 같은 코드가 주어졌고 1 2 3 4 5 6 7 8 9 class Widget { public: Widget(); virtual ~Widget(); virtual std::size_t size() const; virtual void normalize(); void swap(Widget& other); ... }; Colored by Color Scripter 다음의 함수가 있을 때, 1 2 3 4 5 6 7 8 9 void doProcessing(Widget& w) { if(w.size() > 10 && w != so..
